Введение
К решению систем линейных алгебраических уравнений приводятся многие задачи численного анализа.
Известное из курса высшей алгебры правило Крамера для решения систем линейных алгебраических уравнений практически невыгодно, так как требует слишком большого количества арифметических операций и записей. Поэтому было предложено много различных способов, более пригодных для практики.
Используемые практически методы решения систем линейных алгебраических уравнений можно разделить на две большие группы: так называемые точные методы и методы последовательных приближений. Точные методы характеризуются тем, что с их помощью принципиально возможно, проделав конечное число операций, получить точные значения неизвестных. При этом, конечно, предполагается, что коэффициенты и правые части системы известны точно, а все вычисления производятся без округлений. Чаще всего они осуществляются в два этапа. На первом этапе преобразуют систему к тому или иному простому виду. На втором этапе решают упрощенную систему и получают значения неизвестных.
Методы последовательных приближений характеризуются тем, что с самого начала задаются какими-то приближенными значениями неизвестных. Из этих приближенных значений тем или иным способом получают новые «улучшенные» приближенные значения. С новыми приближенными значениями поступают точно также и т.д. При выполнении определенных условий можно придти, вообще говоря, после бесконечного числа шагов. Рассмотрим два точных метода: метод ортогонализации и метод сопряженных градиентов.
1. Метод ортогонализации
1.1 Метод ортогонализации в случае симметрической матрицы
Пусть дана система
(1)
порядка n. Чтобы избежать в дальнейшем путаницы, над векторами поставим черточки. Решение системы будем разыскивать в виде
, (2)
где – n векторов, удовлетворяющих условиям
при (3)
Здесь рассматривается обычное скалярное произведение векторов в n-мерном векторном пространстве, т.е. если и , то . Пусть такие векторы найдены. Как это делается, будет показано ниже. Рассмотрим скалярное произведение обеих частей системы (1) с
(4)
Используя (2) получим:
(5)
или, в силу выбора векторов ,
. (6)
Итак, для определения коэффициентов получили систему с треугольной матрицей. Определитель этой системы равен
. (7)
Следовательно, если , то возможно найти и находятся они без труда.
Особенно легко определятся , если матрица А симметрическая. В этом случае, очевидно,
(8)
и, следовательно,
=0 при . (9)
Тогда система для определения примет вид
(10)
и
. (11)
Метод можно обобщить. Пусть каким-то образом удалось найти систему 2n векторов так, что
=0 при . (12)
Умножая обе части равенства (1) на и используя представление через , как и ранее, получим:
. (13)
Опять получилась система линейных алгебраических уравнений с треугольной матрицей для определения . Несколько усложнив вычисления можно получить систему диагонального вида. Для этого построим три системы векторов , так что имеют место равенства:
(14)
(15)
(16)
Тогда
, (17)
так как при i<r
(18)
и при i>r
(19)
Таким образом,
(20)
Остановимся подробнее на первом из описанных методов. ............
