Численные методы решения систем линейных уравнений (стр. 3 из 6)
При этом линейная функция L1 фактически не зависит от х1.
Зададим какие-либо начальные значения неизвестных (нулевые приближения):
х1(0), х2(0), х3(0), х4(0).
Подставляя эти значения в правые части системы (*), получим первые приближения:
Полученные первые приближения могут быть так же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:
Условия сходимости итерационного процесса.
Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х1, х2, х3, х4.
Не вдаваясь в подробности, скажем, что для того чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.
Это условие можно сформулировать и более точно:
Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:
Итерация Якоби.
Рассмотрим систему линейных уравнений:
Уравнения можно записать в виде:
Это позволяет предложить следующий итерационный процесс:
или (другой вид записи)
Покажем, что если начать с точки P0 = (х1(0), х2(0), х3(0), х4(0)) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х1 = 1, х2 = 2, х2 = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:
Новая точка P1 = (х1(1), х2(1), х3(1), х4(1)) = (1.75, 3.375, 3), ближе, чем P0.
Итерация, использующая (3), генерирует последовательность точек {Pk}, которая сходится к решению (2, 4, 3):
| k | х1(k) | х2(k) | х3(k) |
| 0 | 1.0 | 2.0 | 2.0 |
| 1 | 1.75 | 3.375 | 3.0 |
| 2 | 1.84375 | 3.875 | 3.025 |
| 3 | 1.9625 | 3.925 | 2.9625 |
| 4 | 1.990625 | 3.9765625 | 3.0 |
| 5 | 1.99414063 | 3.9953125 | 3.0009375 |
| … | … | … | … |
| 15 | 1.99999993 | 3.99999985 | 3.0009375 |
| … | … | … | … |
| 19 | 2.0 | 4.0 | 3.0 |
Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем.
Итерация Гаусса-Зейделя.
Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.
Отметим, что итеративный процесс Якоби производит три последовательности – {х1(k)}, {х2(k)}, {х3(k)}, {х4(k)}. Кажется разумным, что х1(k+1) может быть использовано вместо х2(k). Аналогично х1(k+1) и х2(k+1) можно использовать в вычислении х3(k+1). Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):
Такой итерационный процесс даст результаты:
| k | х1(k) | х2(k) | х3(k) |
| 0 | 1.0 | 2.0 | 2.0 |
| 1 | 1.75 | 3.75 | 2.95 |
| 2 | 1.95 | 3.96875 | 2.98625 |
| 3 | 1.995625 | 3.99609375 | 2.99903125 |
| … | … | … | … |
| 8 | 1.99999983 | 3.99999988 | 2.99999996 |
| 9 | 1.99999998 | 3.99999999 | 3.0 |
| 10 | 2.0 | 4.0 | 3.0 |
Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби.
Вывод.
1. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):
Эти формулы как раз и задают собственно итерационный процесс.
2. При этом чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.
Это условие можно сформулировать и более точно:
Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:
3. Следует так же сказать, что итерационный процесс может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.
Практическая часть.
1) Метод обратной матрицы.
| Метод обратной матрицы | ||||||
| x1 | x2 | x3 | x4 | |||
| 12 | -4 | 0 | 6 | 2 | ||
| A= | -4 | 21 | 5 | 3 | B= | 4 |
| -3 | 2 | -22 | 1 | -2 | ||
| -2 | -3 | 5 | 23 | 4 | ||
| 0,083 | 0,013 | -0,002 | -0,023 | |||
| A-1= | 0,016 | 0,048 | 0,009 | -0,011 | ||
| -0,009 | 0,003 | -0,044 | 0,004 | |||
| 0,011 | 0,007 | 0,010 | 0,039 | |||
| x= | 0,129 | |||||
| 0,165 | ||||||
| 0,097 | ||||||
| 0,186 | ||||||
2) Метод Крамера.
| Метод Крамера | ||||||
| x1 | x2 | x3 | x4 | |||
| 12 | -4 | 0 | 6 | 2 | ||
| A= | -4 | 21 | 5 | 3 | B= | 4 |
| -3 | 2 | -22 | 1 | -2 | ||
| -2 | -3 | 5 | 23 | 4 | ||
| 'A'= | -134088 | |||||
| 2 | -4 | 0 | 6 | |||
| A1= | 4 | 21 | 5 | 3 | ||
| -2 | 2 | -22 | 1 | |||
| 4 | -3 | 5 | 23 | |||
| 'A1'= | -17296 | x1= | 0,129 | |||
| 12 | 2 | 0 | 6 | |||
| A2= | -4 | 4 | 5 | 3 | ||
| -3 | -2 | -22 | 1 | |||
| -2 | 4 | 5 | 23 | |||
| 'A2'= | -22188 | x2= | 0,165 | |||
| 12 | -4 | 2 | 6 | |||
| A3= | -4 | 21 | 4 | 3 | ||
| -3 | 2 | -2 | 1 | |||
| -2 | -3 | 4 | 23 | |||
| 'A3'= | -12980 | x3= | 0,097 | |||
| 12 | -4 | 0 | 2 | |||
| A4= | -4 | 21 | 5 | 4 | ||
| -3 | 2 | -22 | -2 | |||
| -2 | -3 | 5 | 4 | |||
| 'A4'= | -24896 | x4= | 0,186 | |||
| x= | 0,129 | |||||
| 0,165 | ||||||
| 0,097 | ||||||
| 0,186 | ||||||
3) Метод Гаусса.
| Метод Гаусса | ||||||
| x1 | x2 | x3 | x4 | |||
| 12 | -4 | 0 | 6 | 2 | ||
| A= | -4 | 21 | 5 | 3 | B= | 4 |
| -3 | 2 | -22 | 1 | -2 | ||
| -2 | -3 | 5 | 23 | 4 | ||
| 'A'= | -134088 | |||||
| 1,000 | -0,333 | 0,000 | 0,500 | 0,167 | ||
| -4,000 | 21,000 | 5,000 | 3,000 | 4,000 | ||
| -3,000 | 2,000 | -22,000 | 1,000 | -2,000 | ||
| -2,000 | -3,000 | 5,000 | 23,000 | 4,000 | ||
| 1,000 | -0,333 | 0,000 | 0,500 | 0,167 | ||
| 0,000 | 25,333 | 5,000 | 5,000 | 4,667 | ||
| 0,000 | 1,000 | -22,000 | 2,500 | -1,500 | ||
| 0,000 | -3,667 | 5,000 | 24,000 | 4,333 | ||
| 1,000 | -0,333 | 0,000 | 0,500 | 0,167 | ||
| 0,000 | 1,000 | 0,197 | 0,197 | 0,184 | ||
| 0,000 | 0,000 | -22,197 | 2,303 | -1,684 | ||
| 0,000 | 0,000 | 5,724 | 24,724 | 5,009 | ||
| 1,000 | -0,333 | 0,000 | 0,500 | 0,167 | ||
| 0,000 | 1,000 | 0,197 | 0,197 | 0,184 | ||
| 0,000 | 0,000 | 1,000 | -0,104 | 0,076 | ||
| 0,000 | 0,000 | 0,000 | 25,317 | 4,574 | ||
| x= | 0,120 | |||||
| 0,130 | ||||||
| 0,095 | ||||||
| 0,181 | ||||||
4) Листинг программы (Метод Крамера, Метод Гаусса, Метод обратной матрицы).
BeginVB.FormfrmAriel
BorderStyle = 1 'Единственный Фиксированный
Caption = "Решение систем линейных уравнений"
ClientHeight = 6315
ClientLeft = 4365
ClientTop = 2430
ClientWidth = 7815
BeginProperty Font
Name = "MS Sans Serif"
Size = 12
Charset = 204
Weight = 700
Underline = 0 'False
Italic = -1 'True
Strikethrough = 0 'False
EndProperty
LinkTopic = "Форма1"
MaxButton = 0 'False
MinButton = 0 'False
ScaleHeight = 6315
ScaleWidth = 7815
Begin VB.TextBox txtMOMZ
Alignment = 2 'ВыравниваниепоЦентру
BeginProperty Font
Name = "Times New Roman"
Size = 15.75
Charset = 204
Weight = 400
Underline = 0 'False
Italic = 0 'False
Strikethrough = 0 'False
EndProperty
Height = 375
Left = 3960
TabIndex = 45
Top = 5520
Width = 975
End
Begin VB.TextBox txtMOMY
Alignment = 2 'ВыравниваниепоЦентру
BeginProperty Font
Name = "Times New Roman"
Size = 15.75
Charset = 204
Weight = 400
Underline = 0 'False
Italic = 0 'False
Strikethrough = 0 'False
EndProperty
Height = 375
Left = 2640
TabIndex = 44
Top = 5520
Width = 975
End
Begin VB.TextBox txtMOMX
Alignment = 2 'ВыравниваниепоЦентру