2939

Решая эту систему линейных уравнений, получаем коэффици-

енты a0 , a1,..., am .

3. Интегральное приближение функции по способу наименьших квадратов. Рассмотрим теперь случай, когда заданную

на промежутке a;b непрерывную функцию надо аппроксимировать обобщенным многочленом:

Таким образом, получим систему уравнений:

51

3. МЕТОДЫ ЧИСЛЕННОГО РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

3.1. МЕТОД ГАУССА

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

Пусть дана система линейных уравнений

52

Рассмотрим общую схему метода Гаусса для систем, имеющих единственное решение.

Предположим, что a11 0 . В противном случае можно поменять местами первое уравнение с уравнением, в котором коэффициент при неизвестном x1 отличен от нуля. Уравнение, с помощью

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

Разделим первое уравнение системы (3.1) на a11 . Оно примет вид

Умножим разрешающее уравнение (3.1) на a21 и вычтем по-

лученное уравнение из второго уравнения системы (3.1). Аналогично преобразуем остальные уравнения. В результате этих операций система запишется так:

Теперь, оставив без изменения первое уравнение системы (3.3) , можно сделать второе уравнение разрешающим и применить описанную процедуру к системе из n 1 уравнений, исключив неиз-

53

вестное x2 из третьего и последующих уравнений. Получим систему вида:

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

системы называют прямым ходом в методе Гаусса. Обратным ходом называется последовательное исключение неизвестных, начиная с (n 1) - го уравнения и заканчивая первым.

54

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

нения, исключая тем самым неизвестное x2 в последнем уравнении. Получим систему

55

Для уменьшения погрешности вычислений существуют различные модификации метода Гаусса. Одна из модификаций метода Гаусса с выбором максимального элемента по столбцу состоит в следующем.

В начале первого шага прямого хода среди коэффициентов ai1 (i 1,2,..., n) при неизвестном x1 находят наибольший по мо-

дулю. Предположим, что это a j1 . После этого в исходной системе

(3.1) можно произвести перестановку: первое уравнение можно поставить на место j - го, а j -е на место первого. Далее вычисления в

описанной ранее последовательности.

В начале второго шага прямого хода максимальный по модулю элемент выбирают среди коэффициентов ai2 (i 1,2,..., n) при неизвестном x2 , снова возможна соответствующая перестановка и исключение неизвестного x2 , начиная с третьего уравнения

т.д., вплоть до последнего шага прямого хода в методе Гаусса. Следует заметить, что процедура прямого хода в методе Гаус-

са может привести не к треугольной матрице (3.4), а к двум другим случаям:

1)число преобразованных уравнений системы меньше числа неизвестных (это происходит, если в процессе преобразований получаются тождества 0=0) – тогда система имеет бесконечное множество решений;

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

3.2.МЕТОД ИТЕРАЦИИ

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

Пусть дана система линейных уравнений (3.1). Введя в рассмотрение матрицы

56

57

Для решения системы (3.6) применим метод последовательных приближений. За начальное приближение принимаем, напри-

мер, столбец свободных членов x(0) .

Далее, последовательно строим матрицы-столбцы

x(1) x(0) , x(2) x(1) ,…. , x(k) x(k 1) , …

Если последовательность приближений x(0) , x(1) ,..., x(k) , ...

имеет предел

n

то этот предел является решением системы (3.6) и, следовательно, решением равносильной системы (3.1)

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

n

j 1

или

n

i 1

58

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

59

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

Условия (3.8), (3.9) сходимости метода итераций накладывают жесткие ограничения на коэффициенты системы (3.6). Однако, если определитель матрицы А не равен нулю, то систему (3.1) с помощью элементарных преобразований всегда можно заменить эквивалентной системой (3.6), для которой условия сходимости будут выполняться. Практически поступают следующим образом. Из заданной системы выделяют уравнения с коэффициентами, модули которых больше суммы модулей остальных коэффициентов уравнения. Каждое выделенное уравне-

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

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

модулю коэффициентом при x2 достаточно составить разность уравнений (1) и (3). Получим уравнение x1 5x2 x3 1 . Под-

60