Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Стационарные итерационные процедуры.

Применение многочленов Чебышева в задаче интерполяции. | Общая постановка задачи и ее разрешимость. | Среднеквадратичное приближение функций алгебраическими многочленами. | Среднеквадратичная ошибка аппроксимации полиномами Лежандра. | Квадратурные формулы на основе интерполяции. | Квадратурные формулы Ньютона-Котеса. | Некоторые общие свойства ортогональных с весом полиномов. | Квадратурные формулы Гаусса-Кристоффеля. | Принцип сжатых отображений. | Метод Ньютона в многомерном случае. |


Читайте также:
  1. Действие (action) - спецификация выполнимого утверждения, которая образует абстракцию вычислительной процедуры.
  2. Логика процедуры. Распространенность функциональной ориентации.
  3. Основные разделы ГКН. Понятия и правила ведения реестра объектов недвижимости. Кадастровые процедуры. Статус кадастровых сведений его изменение.
  4. Порядок выполнения процедуры.

Пусть задана система ЛАУ (23) общего вида (первого рода)

. (1)

Требуется привести данную систему к виду

x=Tx+d (2)

с матрицей (оператором) Т, удовлетворяющей условию в какой либо матричной норме.

Рассмотрим простейший прием такого преобразования – тождественное преобразование:

, ((31)

где Н - некоторая невырожденная матрица.

Из (31) следует, что

x=Tx+d, где .   ((32)

Определение 1. Итерационная процедура, основанная на представлениях (31)-(32)

(5)

называется линейной стационарной итерационной процедурой; при этом матрица Т в представлении (32) называется матрицей перехода, а матрица Н – матрицей расщепления.

Определение 2. Более общая линейная нестационарная итерационная процедура записывается в виде:

,

где Hk – матрица расщепления k-го шага. Соответственно матрица перехода Tk=E-HkA – называется матрицей перехода k-го шага. Рассмотрим некоторые частные случаи стационарных процедур, зависящих от выбора матрицы .

I. Метод простых итераций (Метод Ричардсона).

Положим . Матрица перехода в этом случае имеет вид:

.

Получаем так называемый метод простых итераций или метод Ричардсона.

, или .

Выясним условия сходимости метода Ричардсона.

Пусть - собственное значение матрицы , - собственное значение матрицы . является корнем характеристического уравнения

.

- корнем уравнения

,

или: , откуда следует, что

.

Согласно теореме 3.8. условие сходимости:

.

Последнее условие, например, выполняется, если .

2. Ускоренный метод Ричардсона.

Пусть , где - некоторый параметр сходимости, с помощью которого можно оптимизировать процедуру Ричардсона.

Матрица перехода в этом случае имеет вид:

.

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

Теорема 3.9. Пусть

Тогда и достигается при ,

где - оптимальное значение параметра сходимости ускоренной итерационной процедуры Ричардсона:

.

Т.к. , то все собственные значения матрицы .

Выберем в качестве матричной нормы – спектральную норму . По определению,

,

поэтому чем меньше радиус сходимости, тем быстрее сходится итерационная процедура в соответствии с принципом сжатых отображений.

Пусть - собственное значение матрицы - корень уравнения

.

Пусть - собственное значение матрицы является корнем уравнения

.

Из сравнения двух характеристических уравнений следует:

.

Таким образом,

.

φ(λ)

Обозначим - функция от при фиксированном .

Т.к. функция кусочно линейна, то достигается на концах отрезка, следовательно

.

Найдем такое , для которого

. (33)

Не трудно проверить, что при выполняется следующее условие:

,

т.е. указанное в теореме значение как раз и является оптимальным в смысле критерия (33). Действительно, пусть, например,

Из последних равенств видно, что при любом знаке один из модулей будет , т.е. , что и требовалось доказать.

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

,

где , и .

Т.к. , то , поэтому по свойству 6)

,

а по свойству 7) собственные числа матриц и взаимообратны.

Отсюда следует, что

, ,

и в обозначениях теоремы 3.9. можем записать:

.

Т.о. .

Следствие. Если система первого рода плохо обусловлена (), то и метод Ричардсона сходится плохо и становится чувствительным к возмущениям правой части. В этом случае необходимо перейти к более эффективным методам решения СЛАУ (например, к методу сопряженных градиентов, методу минимизации невязки и др. [1,5]).

 

3. Метод Якоби.

В этом методе приведение системы (23) к виду (27) осуществляется с помощью представления матрицы А в виде:

, (34)

где

-

- диагональная матрица,

-

- строго нижняя (lower) треугольная матрица,

-

- строго верхняя (upper) треугольная матрица.

Подставляя представление (34) в систему (23) Ax=b,получаем:

Dx =(CL+CU) x+b,

откуда следует

,

где матрица перехода имеет вид:

,

, – матрица расщепления.

Получаемый при этом итерационный метод называется методом Якоби. Необходимое условие сходимости: (иначе не существует ).

Достаточные условия сходимости устанавливаются в следующей теореме:

Теорема 3.10. (О сходимости метода Якоби). Пусть матрица - вещественная и удовлетворяет условиям:

.  
. (35)

(Условия (35) называются условиями строгого диагонального преобладания). Тогда метод Якоби сходится.

Условие (35) можно записать в виде:

,

что эквивалентно условию

. (36)

Поскольку

,

то матрица перехода приобретает вид:

.

Воспользуемся строчной нормой матрицы . Согласно (36):

,

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

Замечание. Достаточным условием сходимости метода Якоби является также спектральное условие: .

 

4. Метод Зейделя (Гаусса-Зейделя).

Метод Якоби может быть оптимизирован следующим образом. Как и в методе Якоби воспользуемся разложением матрицы

,  

и запишем систему в виде:

, . (11) (37)

Обозначим

и подставим в (37):

. (12) (38)

Нетрудно убедиться, что при покомпонентной записи уравнения (38):

вектор содержит только первые (i -1) компоненты вектора х, а вектор - содержит компоненты, начиная с (xi +1), т.е.

(13) (39)

При реализации метода последовательных приближений для решения системы (39) естественно использовать в правой части уже найденные значения компонент , полученные в текущей итерации. Алгоритм Гаусса-Зейделя строится следующим образом:

. (14) (40)

Условия сходимости метода Гаусса-Зейделя (40) те же, что и у метода Якоби, но процедура сходится несколько быстрее.

 

5. Метод последовательной верхней релаксации.

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

(15) (41)

где - ускоряющий множитель (параметр релаксации).

Доказано (см, например, [1]), что, если матрица симметрическая и положительно определенная, и , то итерационная процедура (41) сходится, причем существует такое оптимальное значение параметра , при котором достигается максимальное ускорение.

 


Дата добавления: 2015-07-16; просмотров: 97 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Прямые методы решения систем ЛАУ.| Численное дифференцирование на основе интерполяции.

mybiblioteka.su - 2015-2024 год. (0.016 сек.)