Введение
К решению систем линейных алгебраических уравнений приводятсямногие задачи численного анализа.
Известное изкурса высшей алгебры правило Крамера для решения систем линейных алгебраическихуравнений практически невыгодно, так как требует слишком большого количестваарифметических операций и записей. Поэтому было предложено много различныхспособов, более пригодных для практики.
Используемые практически методы решения систем линейныхалгебраических уравнений можно разделить на две большие группы: так называемыеточные методы и методы последовательных приближений. Точные методыхарактеризуются тем, что с их помощью принципиально возможно, проделав конечноечисло операций, получить точные значения неизвестных. При этом, конечно,предполагается, что коэффициенты и правые части системы известны точно, а всевычисления производятся без округлений. Чаще всего они осуществляются в дваэтапа. На первом этапе преобразуют систему к тому или иному простому виду. Навтором этапе решают упрощенную систему и получают значения неизвестных.
Методыпоследовательных приближений характеризуются тем, что с самого начала задаютсякакими-то приближенными значениями неизвестных. Из этих приближенных значенийтем или иным способом получают новые «улучшенные» приближенные значения. Сновыми приближенными значениями поступают точно также и т.д. При выполненииопределенных условий можно придти, вообще говоря, после бесконечного числашагов. Рассмотрим два точных метода: метод ортогонализации и метод сопряженныхградиентов.
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
/> (18)
и при i>r
/> (19)
Такимобразом,
/> (20)
Остановимся подробнее на первом из описанныхметодов. Рассмотрим случай, когда матрица А симметрическая и положительноопределенная. Последнее означает, что для любого вектора /> квадратичная форма егокомпонент /> больше или равна нулю,причем равенство нулю возможно в том и только том случае, если вектор /> нулевой. Как мы виделиранее, нужно построить систему векторов />,удовлетворяющих условиям
/> =0 />. (21)
Это построение можно осуществить следующимобразом. Исходим из какой-то системы линейно независимых векторов />, например из системыединичных векторов, направленных по координатным осям:
/> (22)
Далее проводим «ортогонализацию». Принимаем /> и ищем /> в виде
/>. (23)
Из условия /> находим:
/> (24)
Ищем /> в виде
/>. (25)
Условия /> влекутза собой
/> /> (26)
Далее поступаем также.
Процесс будет осуществим, так как все />. Это же обеспечит намразрешимость системы для определения коэффициентов />.Заметим, что в нашем случае это будет процесс настоящей ортогонализации, если впространстве векторов ввести новое скалярное произведение при помощи соотношения
/>. (26)
Нетрудно проверить, что введенное такимспособом скалярное произведение будет удовлетворять всем требованиям, которые кнему предъявляются.
При решении системы n уравнений по настоящейсхеме требуется произвести
/> (28)
операций умножения и деления.
1.2 Методортогонализации в случае несимметрической матрицы
В случае несимметрической матрицы процессортогонализации проводится точно также. Пусть векторы /> уже построены. Тогда /> ищется в виде
/> (29)
Коэффициенты /> определяютсяиз системы
/> (30)
Система в случае несимметрической матрицы будеттреугольной.
Аналогично строится система «биортогональных»векторов, т.е. система 2n векторов, удовлетворяющих условию (12). При этом /> – n произвольных линейнонезависимых векторов, а векторы /> строятсяпоследовательно в виде
/> (31)
Коэффициенты /> находятсяиз системы
/> (32)
Также поступаем, отыскивая коэффициенты /> и />, при построении системвекторов (14) и (15), удовлетворяющих условиям (16).
При этом получим две системы:
/> (33)
из которых и определяем /> и />.
Остановимся еще на одном методеортогонализации. Будем рассматривать строки матрицы А как векторы:
/> (34)
Ортонормируем эту систему векторов. Первоеуравнение системы /> делим на />. При этом получим
/> (35)
где
/> (36)
Второе уравнение системы заменится на
/> (37)
где
/> (38)
Аналогично поступаем дальше. Уравнение сномером i примет вид
/> (39)
где
/>
/> (40)
Процесс будет осуществим, если системауравнений линейно независима. В результате мы придем к новой системе />, где матрица С будетортогональной, т.е. обладает свойством СС¢=I.
Таким образом, решение системы можно записать ввиде
/>. (41)
Практически, вследствие ошибок округления, СС¢ будет отлична от единичной матрицы и может оказатьсяцелесообразным произвести несколько итераций для системы />.
2. Метод сопряженных градиентов
2.1 Первый алгоритм метода
Пусть требуется решить систему линейныхалгебраических уравнений
/> (1)
с положительно определенной матрицей A порядка n.
Рассмотрим функционал
/>, (2)
представляющий многочлен второго порядкаотносительно x1, x2, …, xn. Обозначим через /> решениесистемы (1), т.е. />. В силусимметричности и положительной определенности матрицы, имеем:
/>
При этом знак равенства возможен лишь при />. Таким образом, задачарешения уравнения (1) сводится к задаче отыскания вектора />, обращающего в минимумфункционал (2).
Для отыскания такого вектора применим следующийметод.
Пусть /> –произвольный начальный вектор, а
/> (4)
– вектор невязок системы. Покажем, чтовектор невязок /> имеет направлениенормали к поверхности />в точке />. В самом деле, направлениенормали совпадает с направлением быстрейшего изменения функции /> в точке />. Это направление мынайдем, если найдем среди векторов />, длякоторых />, такой вектор, что
/>
имеет наибольшее значение. Но
/>
Но среди векторов /> постоянныйдлины /> достигает максимальногозначения, если /> имеетнаправление вектора /> или емупротивоположное. Утверждение доказано. Будем двигаться из точки /> в направлении вектора /> до тех пор, пока функция /> достигает минимальногозначения. Это будет при />, т.е.при
/>. (5)
Вектор
/> (6)
и принимаем за новое приближение к решению.
В методе сопряженных градиентов следующееприближение /> находится так. Через точку/> проведем гиперплоскость (n-1) – гоизмерения
/> (7)
и через /> обозначимновую невязку системы
/>. (8)
Вектор /> направленпо нормали к поверхности /> вточке />, а вектор /> параллелен касательнойплоскости в этой точке. Поэтому
/>. (9)
Гиперплоскость (7) проходит через точку />, так как
/>.
При любом /> вектор/> параллелен некоторойнормальной плоскости к поверхности /> вточке />. Найдем среди них тот,который лежит в гиперплоскости (7), т.е. ортогонален к />. Из условия ортогональностиимеем:
/>,
или
/>. (10)
Вектор
/> (11)
имеет направление нормали к сечению поверхности/> гиперплоскости (7) в точке/>. Будем двигаться из точки /> в направлении вектора /> до тех пор, пока функция /> достигнет минимума. Этобудет при
/>. (12)
Вектор
/>
примем за новое приближение к решению /> системы. Вектор невязок
/> (13)
имеет направление нормали к поверхности /> в точке />. Покажем, что он будетортогонален к /> и />. В самом деле, используя(9), (11), (12), (13), имеем:
/>
Рассмотрим гиперплоскость (n-2) – хизмерений
/>, (14)
проходящую через точку />. Эта гиперплоскостьсодержит и />, так как мы ранее видели,что />, а
/>.
Вектор /> прилюбом /> параллелен гиперплоскости(7), так как
/>.
Подберем /> так,чтобы он был параллелен и гиперплоскости (14), т.е. потребуем ортогональности квектору />. Будем иметь:
/>,
или
/> (15)
Вектор
/> (16)
будет иметь направление нормали к сечениюповерхности />гиперплоскостью (14) вточке />. Из точки /> сместимся в направленииэтого вектора так, чтобы функция /> достигламинимального значения. Это будет при
/>, (17)
/> (18)
примем за новое приближение к />. Новый вектор невязокбудет:
/>. (19)
Продолжая процесс, получим последовательностивекторов />, />, />, определяемыерекуррентными соотношениями:
/> (20)
Для этих векторов имеют место следующиесоотношения:
/> (21)
/> (22)
В самом деле, в силу самого построения при i¹j
/>
Далее, при i>j
/>
Если i=j+1, то правая часть равна нулю, в силу определения />, если же i>j+1, то />, по доказанному, и
/>.
Продолжая понижение индекса у вектора />, через несколько шаговпридем к скалярному произведению /> (поопределению />). Таким образом,соотношения (21) доказаны. Для доказательства (22), в силу равноправия индексовiи j,предположим, что i>j. Тогда
/>.
Так как в n-мерном векторномпространства не может быть более n взаимно ортогональных векторов, то на некотором шаге /> получим />, т.е. /> будет решением системы(1).
На рис. 1 показана геометрическая картинанашего построения при n=3.
/>
Рис. 1
2.2 Второй алгоритм метода
Приведем другой алгоритм метода. Будемобозначать последовательные приближения к решению через /> и введем обозначения:
/>. (23)
Первые два приближения /> и /> возьмем так, чтобы
/>. (24)
Предположим, что уже известно приближение /> (i³1), вычислены /> исправедливо равенство
/>. (25)
Будем искать минимум функционала (2) намножестве векторов
/>. (26)
Приравнивая к нулю частные производные от /> по /> и /> для определения /> и />, получим систему:
/> (27)
или, учитывая (25),
/> (28)
Обозначим через /> решениеэтой системы:
/> (29)
и за (i+1) – е приближение к решениюпримем:
/> (30)
Из системы (27) следует, что
/>, (31)
а так как
/>
то из (31) следует:
/> (32)
Докажем, что если
/> (33)
то при всех i
/> (34)
что будет доказывать и сходимость, и конечностьвторого алгоритма.
В самом деле, при условиях (33)
/>
и
/>
т.е. условие (24) выполнено. Предположим, чтоуже доказаны равенства
/> (35)
и докажем равенство
/>
При предположении (35) /> и,следовательно,
/>
Но из соотношений (20) имеем:
/>
т.е.
/>
Докажем коллинеарность векторов
/> и /> (36)
Из (20) и (29) имеем:
/>
а это и доказывает коллинеарность векторов(36).
Вектор /> даетминимум функционала в плоскости, проходящей через /> инатянутой на векторы /> и />,а мы показали, что этот минимум лежит на прямой, проходящей через /> в направлении вектора />.Но на этой прямой минимум функционала достигается на векторе />. Это и означает, что />
Это и доказывает справедливость (34) при всех i.
На первый взгляд кажется, что первый алгоритмлучше, так как на каждом шаге он требует лишь одного умножения матрицы А навектор />, а во втором алгоритме требуется два умножения матрицы Ана вектор /> и />,но опыт показал, что применение первого алгоритма приводит к быстромунакоплению ошибок округления, так что для матриц большого порядка возможносущественное отклонение от точного решения. Второй алгоритм менее чувствителенк ошибкам округления и поэтому требует меньшего количество шагов для полученияхорошего приближенного решения.
Метод сопряженных градиентов целесообразноиспользовать для решения систем уравнений, в которых матрица А имеет многонулевых элементов. При решении системы по этому методу элементы матрицыучаствуют в арифметических операциях лишь при умножении матрицы на вектор, а умножениематрицы на вектор можно организовать так, чтобы в арифметических операцияхучаствовали только ненулевые элементы.
Заключение
В данной работе были рассмотрены методортогонализации и метод сопряженных градиентов, а также представлена программана языке программирования С++, реализующая метод ортогонализации на ЭВМ, и еерезультаты работы.
Список литературы
1. Березин И.С. и Жидков Н.П. Методывычислений. т. 1. М.: «Наука», 1965. 633c.
2. Воеводин В.В. Численные методы алгебры (теорияи алгоритмы). М.: «Наука», 1966.
3. Подбельский В.В. иФомин С.С. Программирование на языке Си. М.: «Финансы и статистика»,2000. 599 с.
4. Калиткин Н.Н. Численные методы. М.: «Наука»,1978. 512 с.