Численные методы решения систем линейных алгебраических уравнений

      Такие преобразования продолжаются до тех  пор, пока матрица не приведется к верхнее - треугольному виду. Т. е. под главной диагональю не окажутся все нули:

      

      Вспомнив, что каждая строка представляет собой  одно из уравнений линейной системы  уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

      γ_mn*x_n = δ_m.

      Отсюда  легко можно найти значение первого  корня – x_n = δ_m/γ_mn.

      Подставив это значение в предыдущее m-1-е  уравнение, легко получим значение x_n-1-ого корня.

      Таким образом, поднимаясь до самого верха  обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений [5]. 

      Пример 1

      Рассмотрим  систему уравнений:

      

      Главный определитель данной системы: 

      

      Δ = [1*(-4)*(-2)+2*2*1+(-1)*(-1)*(-1)]-[1*(-4)*(-1)+2*(-1)*(-2)+2*(-1)*1] = [8+4-1]-[4+4-2] = 11-6 =5,

      т. е. Δ ≠ 0.

      Т. е. система определена и разрешима. Решим ее по методу Гаусса.

      Проведем  прямой ход метода Гаусса, выписав  предварительно расширенную матрицу  системы:

      

      Получим нули под главной диагональю в  первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C₂-(a₂₁/a₁₁)*C₁ = C₂-(2/1)*C₁ = C₂-2*C₁:

      

      Аналогично  поступаем и с элементом а31 (т. е. под диагональю в третьей  строке матрицы). Третью строку матрицы  преобразуем по формуле C₃-(a₃₁/a₁₁)*C₁ = C₃-(-1/1)*C₁ = C₃+C₁:

      

      Таким образом, мы получили нули под главной  диагональю в первом столбце расширенной  матрицы. Осталось получить нуль под  главной диагональю во втором столбце  матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C₃-(a₃₂/a₂₂)*C₂ = C₃-(1/-2)*C₂ = C₃+1/2C₂:

        

      Таким образом, проведя прямой ход метода Гаусса, мы получили расширенную матрицу системы, приведенную к верхне-треугольному виду:

      

      Эта матрица эквивалентна системе:

      

      Обратным  ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х₃:

      -5/2x₃ = 3/2,

      x₃ = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.

      Корень x₃ = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x₂-3x₃ = 1):

      -2x₂-3(-3/5) = 1,

      -2x₂+9/5 = 1,

      -2x₂ = 1-9/5,

      -2x₂ = -4/5,

      x₂ = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.

      Корень x₂ = 2/5 найден. Подставим его и корень х₃ в верхнее (первое) уравнение системы (x₁-x₂+x₃ = 0):

      x₁-2/5+(-3/5) = 0,

      x₁-5/5 = 0,

      x₁ = 5/5 = 1.

      Проверка:

        

      т. е.

      

      т. е.

      

      и т. д [9].

      Вывод: Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхнее - треугольной матрицей. Эти действия называют прямым ходом.
2. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).
3. При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее - треугольному виду в прямом ходе метода.

 

3.   Итерация для линейных систем

 
 

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

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

      

      Разрешим  первое уравнение системы относительно х₁:

      х₁ = (-a₁₂/a₁₁)х₂-a₁₃/a₁₁х₃-a₁₄/a₁₁х₄-a₁₅/a₁₁.

      Затем разрешим второе уравнение относительно х₂ и т. д. Тогда систему можно переписать в виде:

      

      где α = -a_ik/a_ii, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

      Система является частным случаем записи вида:

      

      При этом линейная функция L₁ фактически не зависит от х₁.

      Зададим какие-либо начальные значения неизвестных (нулевые приближения):

      х₁⁽⁰⁾, х₂⁽⁰⁾, х₃⁽⁰⁾, х₄⁽⁰⁾.

      Подставляя  эти значения в правые части системы (*), получим первые приближения:

      

      Полученные  первые приближения могут быть так  же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:

      

      Условия сходимости итерационного процесса. 

      Установим условия, выполнение которых обеспечит  сходимость получающихся приближений  к истинному (точному) решению системы  х₁, х₂, х₃, х₄.

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

      Это условие можно сформулировать и  более точно [20]:

      Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:

        

      1.4 Итерация Якоби 
 

      Рассмотрим  систему линейных уравнений:

      

      Уравнения можно записать в виде:

      

      Это позволяет предложить следующий итерационный процесс:

      

      или (другой вид записи) 

      

      Покажем, что если начать с точки P₀ = (х₁⁽⁰⁾, х₂⁽⁰⁾, х₃⁽⁰⁾, х₄⁽⁰⁾) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х₁ = 1, х₂ = 2, х₂ = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

      

      Новая точка P₁ = (х₁⁽¹⁾, х₂⁽¹⁾, х3⁽¹⁾, х₄⁽¹⁾) = (1.75, 3.375, 3), ближе, чем P₀.

      Итерация, использующая (3), генерирует последовательность точек {P_k}, которая сходится к решению (2, 4, 3):

      Этот  процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем [19]. 

      1.5 Итерация Гаусса-Зейделя 
 

      Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

      Отметим, что итеративный процесс Якоби  производит три последовательности – {х₁^(k)}, {х₂^(k)}, {х₃^(k)}, {х₄^(k)}. Кажется разумным, что х₁^(k+1) может быть использовано вместо х₂^(k). Аналогично х₁^(k+1) и х₂^(k+1) можно использовать в вычислении х₃^(k+1). Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):

      

      Такой итерационный процесс даст результаты: 
 

 

      Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби [19]. 
 

      Вывод:

1. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):