Реферат: Программирование системы уравнений

--PAGE_BREAK--2: Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной. Условие совместности.
Упомянутое выше условие <img border=«0» width=«72» height=«20» src=«ref-1_1640215703-430.coolpic» alt="\beta_{r+1}= 0\!" v:shapes="_x0000_i1035">может быть сформулировано в качестве необходимого и достаточного условия совместности:

Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

1) На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получавшуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

2) На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

В простейшем случае алгоритм выглядит так:
<img border=«0» width=«419» height=«95» src=«ref-1_1640225524-3231.coolpic» alt="\left\{\begin{array}{lcc} a_{11} \cdot x_1 + a_{12} \cdot x_2 + \ldots + a_{1n} \cdot x_n & = b_1 & (1) \\ a_{21} \cdot x_1 + a_{22} \cdot x_2 + \ldots + a_{2n} \cdot x_n & = b_2 & (2) \\ \ldots & & \\a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + \ldots + a_{mn} \cdot x_n & = b_m & (m) \end{array}\right." v:shapes="_x0000_i1036">
·                     Прямой ход:

<img border=«0» width=«579» height=«177» src=«ref-1_1640228755-17087.coolpic» alt="\begin{array}{ccc}(2)\to (2)-(1) \cdot ( \frac {a_{21}}{a_{11}}) &:& a_{22}^{\prime} \cdot x_2 + a_{23}^{\prime} \cdot x_3 + \ldots + a_{2n}^{\prime} \cdot x_n = b_2^{\prime} \\(3)\to (3)-(1) \cdot ( \frac {a_{31}}{a_{11}}) &:& a_{32}^{\prime} \cdot x_2 + a_{33}^{\prime} \cdot x_3 + \ldots + a_{3n}^{\prime} \cdot x_n = b_3^{\prime} \\\ldots & & \\(m)\to (m)-(1) \cdot ( \frac {a_{m1}}{a_{11}}) &:& a_{m2}^{\prime} \cdot x_2 + a_{m3}^{\prime} \cdot x_3 + \ldots + a_{mn}^{\prime} \cdot x_n = b_3^{\prime} \\(3)\to (3)-(2) \cdot ( \frac {a_{32}^{\prime}}{a_{22}^{\prime}}) &:& a_{33}^{\prime\prime} \cdot x_3 + \ldots + a_{3n}^{\prime\prime} \cdot x_n = b_3^{\prime\prime} \\\ldots & & \\(m)\to (m)-(m-1) \cdot ( \frac {a_{m,n-1}^{(m-1)}}{a_{m-1,n-1}^{(m-1)}}) &:& a_{mm}^{(m)} \cdot x_m + \ldots + a_{mn}^{(m)} \cdot x_n = b_m^{(m)}\end{array}" v:shapes="_x0000_i1037">
3) Обратный ход. Из последнего ненулевого уравнения выражаем базисную переменную через небазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру для всех базисных переменных, получаем фундаментальное решение.

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:

1) нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: <img border=«0» width=«42» height=«20» src=«ref-1_1640245842-388.coolpic» alt="[A|E]\!" v:shapes="_x0000_i1038">, после чего <img border=«0» width=«15» height=«15» src=«ref-1_1640246230-238.coolpic» alt=«A\!» v:shapes="_x0000_i1039">приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица: <img border=«0» width=«62» height=«23» src=«ref-1_1640246468-446.coolpic» alt="[E|A^{-1}]\!" v:shapes="_x0000_i1040">);

2) определения ранга матрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равен числу её главных переменных);

3) численного решения СЛАУ в вычислительной технике (ввиду погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент).

В отличие от матричного метода и метода Крамера, метод Гаусса может быть применен к системам линейных уравнений с произвольным числом уравнений и неизвестных. Суть метода заключается в последовательном исключении неизвестных.

Система т линейных уравнений с п неизвестными имеет вид:
<img border=«0» width=«240» height=«88» src=«ref-1_1640246914-1022.coolpic» v:shapes="_x0000_i1042">
x1, x2, …, xn– неизвестные.

ai

j
— коэффициенты при неизвестных.

bi— свободные члены (или правые части)

Система линейных уравнений называется совместной, если она имеет решение, и несовместной, если она не имеет решения.

Совместная система называется определенной, если она имеет единственное решение и неопределенной, если она имеет бесчисленное множество решений.

Две совместные системы называются равносильными, если они имеют одно и то же множество решений.

К элементарным преобразованиям системы отнесем следующее:

1) перемена местами двух любых уравнений;

2) умножение обеих частей любого из уравнений на произвольное число, отличное от нуля;

3) прибавление к обеим частям одного из уравнений системы соответствующих частей другого уравнения, умноженных на любое действительное число.

Элементарные преобразования переводят систему уравнений в равносильную ей.

Элементарные преобразования системы используются в методе Гаусса.

Для простоты рассмотрим метод Гаусса для системы трех линейных уравнений с тремя неизвестными в случае, когда существует единственное решение:

Дана система:
<img border=«0» width=«197» height=«75» src=«ref-1_1640247936-880.coolpic» v:shapes="_x0000_i1043">                          ( 1 )
1-ый шаг метода Гаусса.

На первом шаге исключим неизвестное х1 из всех уравнений системы (1), кроме первого. Пусть коэффициент <img border=«0» width=«51» height=«23» src=«ref-1_1640248816-146.coolpic» v:shapes="_x0000_i1044">. Назовем его ведущим элементом. Разделим первое уравнение системы (1) на а11. Получим уравнение:
<img border=«0» width=«191» height=«28» src=«ref-1_1640248962-379.coolpic» v:shapes="_x0000_i1045">             ( 2 )
где <img border=«0» width=«253» height=«48» src=«ref-1_1640249341-502.coolpic» v:shapes="_x0000_i1046">

Исключим х1 из второго и третьего уравнений системы (1). Для этого вычтем из них уравнение (2), умноженное на коэффициент при х1 (соответственно а21 и а31).


Система примет вид:
<img border=«0» width=«203» height=«83» src=«ref-1_1640249843-991.coolpic» v:shapes="_x0000_i1047">         ( 3 )
Верхний индекс (1) указывает, что речь идет о коэффициентах первой преобразованной системы.
2-ой шаг метода Гаусса.

На втором шаге исключим неизвестное х2из третьего уравнения системы (3). Пусть коэффициент <img border=«0» width=«67» height=«27» src=«ref-1_1640250834-183.coolpic» v:shapes="_x0000_i1048">. Выберем его за ведущий элемент и разделим на него второе уравнение системы (3), получим уравнение:
<img border=«0» width=«137» height=«28» src=«ref-1_1640251017-290.coolpic» v:shapes="_x0000_i1049">                    ( 4 )
где <img border=«0» width=«228» height=«53» src=«ref-1_1640251307-574.coolpic» v:shapes="_x0000_i1050">

Из третьего уравнения системы (3) вычтем уравнение (4), умноженное на <img border=«0» width=«44» height=«28» src=«ref-1_1640251881-150.coolpic» v:shapes="_x0000_i1051">Получим уравнение: <img border=«0» width=«116» height=«28» src=«ref-1_1640252031-261.coolpic» v:shapes="_x0000_i1052">

Предполагая, что <img border=«0» width=«72» height=«28» src=«ref-1_1640252292-191.coolpic» v:shapes="_x0000_i1053">находим<img border=«0» width=«115» height=«53» src=«ref-1_1640252483-351.coolpic» v:shapes="_x0000_i1054">

В результате преобразований система приняла вид:
<img border=«0» width=«201» height=«83» src=«ref-1_1640252834-812.coolpic» v:shapes="_x0000_i1055">                 (5)
Система вида (5) называется треугольной.

Процесс приведения системы (1) к треугольному виду (5) (шаги 1 и 2) называют прямым ходом метода Гаусса.

Нахождение неизвестных из треугольной системы называют обратным ходом метода Гаусса.

Для этого найденное значение х3 подставляют во второе уравнение системы (5) и находят х2. Затем х2 и х3 подставляют в первое уравнение и находят х1.

В общем случае для системы т линейных уравнений с п неизвестными проводятся аналогичные преобразования. На каждом шаге исключается одно из неизвестных из всех уравнений, расположенных ниже ведущего уравнения.

Отсюда другое называние метода Гаусса – метод последовательного исключения неизвестных.

Если в ходе преобразований системы получается противоречивое уравнение вида 0 = b, где b¹0, то это означает, что система несовместна и решений не имеет.

В случае совместной системы после преобразований по методу Гаусса, составляющих прямой ход метода, система т линейных уравнений с п неизвестными будет приведена или к треугольному или к ступенчатому виду.

Треугольная система имеет вид:
<img border=«0» width=«197» height=«88» src=«ref-1_1640253646-714.coolpic» v:shapes="_x0000_i1056">
Такая система имеет единственное решение, которое находится в результате проведения обратного хода метода гаусса.


Ступенчатая система имеет вид:
<img border=«0» width=«189» height=«88» src=«ref-1_1640254360-777.coolpic» v:shapes="_x0000_i1057">
Такая система имеет бесчисленное множество решений. Чтобы найти эти решения, во всех уравнениях системы члены с неизвестными хk+1, …, xkпереносят в правую часть. Эти неизвестные называются свободными и придают им произвольные значения. Из полученной треугольной системы находим х1, …, xk, которые будут выражаться через свободные неизвестные. Подробнее об этом можно узнать в рекомендуемой литературе.

Рассмотренный метод Гаусса легко программируется на ЭВМ и является более экономичным (по числу действий), чем другие методы.
3 Решение уравнения методами Ньютона, Хорд
Метод хорд(способ пропорциональных частей) — численный метод уточнения корня трансцендентного уравнения.

Точный корень <img border=«0» width=«9» height=«18» src=«ref-1_1640255137-226.coolpic» alt="~\xi" v:shapes="_x0000_i1058">уравнения <img border=«0» width=«70» height=«21» src=«ref-1_1640255363-484.coolpic» alt="~f(\xi)=0" v:shapes="_x0000_i1059">находится на отрезке <img border=«0» width=«39» height=«21» src=«ref-1_1640255847-387.coolpic» alt="~(a,b)" v:shapes="_x0000_i1060">. Производная <img border=«0» width=«41» height=«22» src=«ref-1_1640256234-395.coolpic» alt="~f'(x)" v:shapes="_x0000_i1061">на этом промежутке непрерывна и сохраняет постоянный знак. Приближенный корень <img border=«0» width=«11» height=«12» src=«ref-1_1640256629-219.coolpic» alt="~\bar{x}" v:shapes="_x0000_i1062">, при котором <img border=«0» width=«72» height=«20» src=«ref-1_1640256848-549.coolpic» alt="~f(\bar{x})\approx0" v:shapes="_x0000_i1063">, можно найти используя метод хорд. Для этого нужно взять начальное приближение корня <img border=«0» width=«22» height=«15» src=«ref-1_1640257397-1053.coolpic» alt="~x_0" v:shapes="_x0000_i1064">и применить к нему итерационную формулу:

линейный уравнение хорда гаусс ньютон

<img border=«0» width=«213» height=«47» src=«ref-1_1640258450-1364.coolpic» alt="~x_{i+1}=x_i-\frac{f(x_i)(b-x_i)}{f(b)-f(x_n)}" v:shapes="_x0000_i1065">, <img border=«0» width=«55» height=«12» src=«ref-1_1640259814-325.coolpic» alt="~x_0=a" v:shapes="_x0000_i1066">, если <img border=«0» width=«120» height=«22» src=«ref-1_1640260139-749.coolpic» alt="~f''(a)\,f(a)<0" v:shapes="_x0000_i1067">

<img border=«0» width=«215» height=«47» src=«ref-1_1640260888-1358.coolpic» alt="~x_{i+1}=x_i-\frac{f(x_i)(x_i-a)}{f(x_n)-f(a)}" v:shapes="_x0000_i1068">, <img border=«0» width=«55» height=«12» src=«ref-1_1640259814-325.coolpic» alt="~x_0=a" v:shapes="_x0000_i1069">, если <img border=«0» width=«116» height=«22» src=«ref-1_1640262571-760.coolpic» alt="~f''(b)\,f(b)<0" v:shapes="_x0000_i1070">


Погрешность вычислений:
<img border=«0» width=«184» height=«44» src=«ref-1_1640263331-964.coolpic» alt="~\left|\xi-x_{i+1}\right|\le\frac{M_1-m_1}{m_1}" v:shapes="_x0000_i1071">, <img border=«0» width=«163» height=«35» src=«ref-1_1640264295-1824.coolpic» alt="~M_1=\max\limits_{x\in(a,b)}\left|f'(x)\right|" v:shapes="_x0000_i1072">, <img border=«0» width=«153» height=«33» src=«ref-1_1640266119-982.coolpic» alt="~m_1=\min\limits_{x\in(a,b)}\left|f'(x)\right|" v:shapes="_x0000_i1073">
В отличие от метода дихотомии, обращающего внимание лишь на знаки значений функции, но не на сами значения, метод хорд использует пропорциональное деление интервала (рисунок 1).
<img border=«0» width=«598» height=«238» src=«ref-1_1640267101-13642.coolpic» alt=«Рис. 6. Метод хорд & Рис.7. Метод касательных» v:shapes="_x0000_i1074">



Здесь вычисляются значения функции на концах отрезка и строится “хорда”, соединяющая точки (a, f(a)) и (b, f(b)). Точка пересечения ее с осью абсцисс
<img border=«0» width=«176» height=«51» src=«ref-1_1640280743-769.coolpic» v:shapes="_x0000_i1075">
принимается за очередное приближение к корню. Анализируя знак f(z) в сопоставлении со знаком f(x) на концах отрезка, сужаем интервал до [a,z] или [z,b] и продолжаем процесс построения хорд до тех пор, пока разница между очередными приближениями не окажется достаточно малой (в пределах допустимой погрешности) |Zn-Zn-1|<<img border=«0» width=«15» height=«17» src=«ref-1_1640281512-313.coolpic» v:shapes="_x0000_i1076">.

Можно доказать, что истинная погрешность найденного приближения:
<img border=«0» width=«259» height=«45» src=«ref-1_1640281825-826.coolpic» v:shapes="_x0000_i1077">,
    продолжение
--PAGE_BREAK--