Методы решения алгебраических уравнений (стр. 3 из 6)

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |qik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk(k-1). После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.

Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.

На 1-м шаге метода среди элементов aij определяют максимальный по модулю элемент ai1j1. Первое уравнение системы и уравнение с номером i1 меняют местами. Далее стандартным образом производят исключение неизвестного xi1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов aij(k–1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент aikjk(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn, xjn–1, …, xj1.

3. Метод Зейделя 3.2.1. Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений

Ax = b

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

x = Bx + c.

Здесь B – квадратная матрица с элементами bij (i, j = 1, 2, …, n), c – вектор-столбец с элементами cij(i = 1, 2, …, n).

В развернутой форме записи система имеет следующий вид:

x1 = b11x1 + b12x2 + b13x3 + … + b1nxn + c1

x2 = b21x1 + b22x2 + b23x3 + … + b2nxn + c2

xn = bn1x1 + bn2x2 + bn3x3 + … + bnnxn + cn

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x1:

x1 = a11–1 (b1 – a12x2 – a13x3 – … – a1nxn),

из второго уравнения – неизвестное x2:

x2 = a21–1 (b2 – a22x2 – a23x3 – … – a2nxn),

и т. д. В результате получим систему

x1 = b12x2 +b13x3 +… +b1,n–1xn–1 +b1nxn+c1 ,

x2 = b21x1 +b23x3 +… +b2,n–1xn–1 +b2nxn+c2 ,

x3 = b31x1 +b32x2 +… +b3,n–1xn–1 +b3nxn+c3 ,

xn = bn1x1 +bn2x2 +bn3x3 +… +bn,n–1xn–1 +cn ,

в которой на главной диагонали матрицы Bнаходятся нулевые элементы. Остальные элементы выражаются по формулам

bij = –aij / aii, ci = bi / aii (i, j = 1, 2, …, n, j ≠ i)

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

Описание метода. Введем нижнюю и верхнюю треугольные матрицы

000…00b12b13…b1n

B1 =b2100…0B2 =00b23…b2n

b31b320…0, 000…b3n

bn1bn2bn3…0000…0

Заметим, что B=B1+B2 и поэтому решение x исходной системы удовлетворяет равенству

x = B1x + B2x + c.

Выберем начальное приближение x(0) = [x1(0), x2(0), …, xn(0)]T. Подставляя его в правую часть равенства при верхней треугольной матрице B2и вычисляя полученное выражение, находим первое приближение

x(1) = B1x(0) + B2x(1)

Подставляя приближение x(1), получим

x(2) = B1x(1) + B2x(2)

Продолжая этот процесс далее, получим последовательность x(0), x(1), …, x(n), … приближений к вычисляемых по формуле

x(k+1) = B1(k+1) + B2(k) + c

или в развернутой форме записи

x1(k+1) =b12x2(k) +b13x2(k) +… +b1nxn(k) +c1 ,

x2(k+1) =b21x1(k+1) +b23x3(k) + … +b2nxn(k) +c2 ,

x3(k+1) =b31x1(k+1) +b32x2(k+1) +… +b3nxn(k) +c3 ,

xn(k+1) =bn1x1(k+1) +bn2x2(k+1) +bn3x3(k+1) +… +cn.

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

xi(k+1) = xi(k) – aii–1(∑j=1i–1 aijxj(k+1) + ∑j=1naijxi(k) – bi).

Тогда достаточным условием сходимости метода Зейделя будет

∑j=1, j≠in | aij| < | aii|

(условие доминирования диагонали).

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.

4. Метод Жордана - Гаусса.

Схема с выбором главного элемента состоит в том, что требование неравенства нулю диагональных элементов akk, на которые происходит деление в процессе исключения, заменятся более жестким: из всех элементов К-го столба выбрать наибольший по модулю и переставить уравнения так, чтобы этот элемент оказался на месте элемента акк. Выбор главного элемента и связанная с ним перестановка строк необходимы в тех случаях, когда на каком-либо i-ом шаге акк=0 либо же акк очень мало по остальными элементами i- го столбца: при делении на такое «малое» акк будут получаться большие числа с большими абсолютными погрешностями, в результате чего решение может сильно исказиться.

Ниже излагается алгоритм полного исключения неизвестных или метод Жордана – Гаусса. Суть метода состоит в том, что, рассмотрев первое уравнение, в нем неизвестное с коеффициэнтом, отличным от нуля (в дальнейшем разрешающий элемент ), и разделив первое уравнение на этот коэффициент, с помощью первого уравнения исключают это неизвестное из всех уравнений, кроме первого. Выбрав во втором уравнении неизвестное с коэффициентом, отличным от нуля, и разделив на него второе уравнение, с помощью второго исключают другие неизвестные из всех уравнений, кроме второго и т.д., т.е. с помощью одного уравнения производят полное исключение одного неизвестного. Процесс продолжается до тех пор, пока не будут использованы все уравнения.

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

1. В процессе исключений левая часть I –го уравнения системы обращается в нуль, а правая часть равна некоторому числу, отличному от нуля. т.е. 0

2+ =bc 0.

Это означает, что система не имеет решений, так как I – му уравнению не могут удовлетворять никакие значения неизвестных;

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

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

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

a11x1 + a12x2 + … + a1nxn = b1,n+1

a21x1 + a22x2 + … + a2nxn = b2,n+1

am1x1 + am2x2 + … + amnxn = bm.n+1

Здесь x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn — коэффициенты системы — и b1, b2, … bm — свободные члены — предполагаются известными. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Система (1) называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) — совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества.

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у нее нет ни одного решения.

Совместная система вида (1) может иметь одно или более решений.

Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).

Совместная система вида (1) называется определенной, если она имеет единственное решение; если же у нее есть хотя бы два различных решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой.

Решим следующую систему уравнений:

Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:

Проведём следующие действия:

· К строке 2 добавим: -4 * Строку 1.

· К строке 3 добавим: -9 * Строку 1.

Получим:

· К строке 3 добавим: -3 * Строку 2.

· Строку 2 делим на -2

· К строке 1 добавим: -1 * Строку 3.

· К строке 2 добавим: -3/2 * Строку 3.

· К строке 1 добавим: -1 * Строку 2.

В правом столбце получаем решение:

.

3. Математическая обработка результатов опыта. Аппроксимация функций. Полином Лагранжа. Метод наименьших квадратов

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