Xreferat.com » Рефераты по математике » Метод ортогонализации и метод сопряженных градиентов

Метод ортогонализации и метод сопряженных градиентов

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 с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: