49437 (Численные методы решения систем линейных уравнений), страница 2

Решение

Запишем главный и побочные определители системы:

Вычислим эти определители:

Δ = 3*4*(-4)+7*(-3)*5+(-2)*(-8)*5-5*4*5-3*(-3)*(-8)-7*(-2)*(-4) = 48-105+80-100-72-56 = 128-333 = -205.

Δ1 = -112+(-45)+(-192)-(-240)-24-168 = -112-45-192+240-24-168 = 240-541 = -301.

Δ2 = -36-420-280-75+196-288 = 196-1099 = -903.

Δ3 = -144-147-30-140+27-168 = -629+27 = -602.

Главный определитель системы не равен нулю. Находим неизвестные по формулам Крамера.

Подставим найденные значения определителей в формулы Крамера:

x1 = Δ1/Δ = -301/(-205) = 1,468292682927 ≈ 1,47;

x2 = Δ2/Δ = -903/(-205) = 4,40487804878 ≈ 4,4;

x3 = Δ3/Δ = -602/(-205) = 2,936585365854 ≈ 2,93.

Вывод.

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

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

Если в главном определителе системы заменить поочередно столбцы коэффициентов при x₁, x₂,...x_n на столбец свободных членов, то получим n дополнительных определителей (для каждого из n неизвестных):

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

Метод Гаусса – прямой и обратный ход.

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

Будем считать, что a₁₁ ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:

C₂-(a₂₁/a₁₁)*C₁,

...

C_m-(a_m1/a₁₁)*C₁,

т.е. Ci-(a_i1/a₁₁)*C₁, i = 2, 3, ..., m.

Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а₁₁.

В результате получим матрицу:

Т. е. первая строка осталась без изменений, а в столбце под а₁1 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – a_ij, где I = j.

Повторим наши элементарные преобразования, но уже для элемента α₂₂.

C₁-(a₁₂/α₂₂)*C₂,

...

C_m-(α_m2/α₂₂)*C₂,

т.е. C_i-(α_i2/α₂₂)*C₂, i = 3, ..., m.

Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α₂₂.

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

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

γ_mn*x_n = δ_m.

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

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

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

Пример 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.

Проверка:

т. е.

т. е.

и т. д.

Вывод.

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

1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхне-треугольной матрицей. Эти действия называют прямым ходом.

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

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₁ фактически не зависит от х₁.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Покажем, что если начать с точки 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):

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

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

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

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

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

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