Итерационные методы и общий подход к оптимизации стационарных итерационных методов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

РЕФЕРАТ

Работа выполнена на 62 страницах. Представлено: 6 рисунков, 8 использованных источников.

Ключевые слова: стационарная задача, итерационный метод, точность решения, итерационные параметры, асимптотическая скорость сходимости.

Объект исследования -оптимальные итерационные процессы.

Цель работы - рассмотреть итерационные методы и общий подход к оптимизации стационарных итерационных методов с точки зрения их асимптотического поведения.

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

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. Общие понятия теории итерационных методов

2. Итерационные методы первого порядка

3. Итерационные методы второго порядка

4. Некоторые итерационные методы и их оптимизация

4.1 Простейший итерационный метод

4.2 Сходимость и оптимизация стационарных итерационных методов

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

4.4 Чебышевский итерационный метод

5. Нестационарные итерационные методы

5.1 Теоремы сходимости

5.2 Метод минимальных невязок

5.3 Метод сопряженных градиентов

6. Итерационные методы уточнения корней

6.1 Метрические пространства и принцип сжимающих отображений

6.2 Метод простой итерации

6.3 Методы Ньютона

7. Итерационные методы линейных алгебраических уравнений

7.1 Метод простой итерации для системы линейных алгебраических уравнений

7.2 Метод Зейделя

8. Приближенные методы решения систем нелинейных уравнений

8.1 Метод простой итерации для нелинейных уравнений

8.2 Метод Ньютона

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ В

ВВЕДЕНИЕ

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

Пусть имеется задача

где

Вместо этой задачи рассмотрим нестационарную

Представим в виде

где

а и -- биортогональный базис. Тогда известными приемами приходим к задачам для коэффициентов Фурье:

с одной стороны, и

с другой. Решая эти задачи, получим

В предположении вещественности спектра оператора A имеем . Отсюда следует, что Если оператор стационарной задачи имеет спектр произвольной структуры, то в этом случае такой простой и прозрачной связи между решениями задач уже может не быть.

Разумеется, нестационарную задачу для новой функции можно решать разностными методами по t, например

Тогда

Если нашей целью является решение стационарной задачи, то при определенном соотношении между ф и в(A) имеем

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

1. Общие понятия теории итерационных методов

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

(1.1)

где А--матрица, а f и ц - векторы. [2,c. 162]

Большинство итерационных методов, которые применяются для решения линейных систем, могут быть объединены общей формулой

(1.2)

где-последовательность невырожденных матриц, а -- последовательность вещественных параметров. Если ввести обозначение , то процесс (1.2) можно записать в эквивалентном виде:

(1.3)

Векторы называются векторами невязок итерационного метода (1.2), а векторы -- точное решение системы (1.1)) называются векторами ошибок этого метода. Вычитая из обеих частей соотношения (1.3) вектор и делая замену f =A, приходим к соотношению для последовательности векторов ошибок:

(1.4)

где матрица

(1.5)

называется оператором j-го шага итерационного метода (1.2). Умножая (1.4) на матрицу А, приходим к соотношению для последовательности векторов невязок

(1.6)

Мы будем называть итерационный метод (1.2) сходящимся, если последовательность { } сходится к точному решению системы (1.1) при любом начальном векторе, и расходящимся -- в противном случае. Очевидно, что необходимым и достаточным условием сходимости итерационного метода (1.2) является сходимость последовательностей { } и {} к нулевому вектору для любых и (A .

Итерационный метод (1.2) называется стационарным, если матрица не зависит от номера итерации (оператор является постоянной матрицей), и нестационарным -- в противном случае. Особо мы выделим класс циклических итерационных методов, которые могут быть отнесены как к стационарным, так и к нестационарным итерационным методам.

Циклическими мы будем называть итерационные методы, которые обладают свойством для любого j и некоторого фиксированного s Нетрудно видеть, что, объединяя каждые s последовательных итераций в одну, мы приходим к стационарному итерационному процессу вида где Н определяется из уравнения

 (1.7)

где определяется из уравнения

(1.8)

С другой стороны, в первоначальной формулировке циклические итерационные методы относятся к нестационарным.

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

(1.9)

которая мажорирует сверху целевую функцию и в определенном смысле достаточно хорошо ее приближает. В предположении, что при любом H_j из заданного класса одна итерация метода (1.2) требует одно и то же число арифметических и логических действий W₀, оказывается целесообразным определить W соотношением

, (1.10)

где итераций метода (1.2), достаточных для уменьшения некоторой нормы начальной ошибки в раз. Иначе говоря, равно числу итераций метода (1.2), достаточных для решения системы (1.1) с точностью , если норма вектора ошибки равна единице. В дальнейшем на конкретных примерах мы покажем, как определяется функционал N и решается задача его минимизации.

2. Итерационные методы первого порядка

Начнём с построения экстремального полинома P(a₁^*;z) на множестве D, состоящем из двух точек z₁ и z₂ :

Пусть а угол

определим равенствами

[1, c. 63]

Теорема 1.1

Экстремальным в классе полиномов P(a₁;z), zD, является полином P(a₁^*;z), где

,

при этом

Доказательство.

Проведём из середины отрезка t[z₁,z₂] прямую, перпендикулярную отрезку z₁z₂ и найдём точку пересечения этой прямой с единичной окружностью, ближайшую к точке Эта точка m(t) обеспечит равенство Для этого составим уравнение

В развернутом виде это уравнение запишется следующим образом:

Решая последнее уравнение относительно s, получаем

В случае,если cos д=0, s определяется равенством

и, следовательно,

Пусть , тогда если , то

Очевидно, что минимум функции R(t) достигается при

В общем случае

Для нахождения минимального значения R(t) найдём производную

Найдем критические точки функции R²(t); для этого приравняем производную к нулю и приведём полученное уравнение к виду:

После возведения обеих частей полученного уравнения в квадрат, получаем:

то есть

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

на a²b+h² получаем, что

Кроме того, , так как

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

при минимальном значении R(t_*), определяется равенством:

и, следовательно, поворот на , осуществляемый множителем , приводит к экстремальному полиному

Заметим, что две точки z₁ и z₂ формируют круг зависимости Q с центром в точке t^-1_*R(t_*) и радиусом p=t^-1_*R(t_*), обладающим тем свойством, что любое подмножество M, для которого {z₁,z₂} MQ имеет тот же самый экстремальный полином.

Теорема 1.2

Полином P(a^*₁;z), где является экстремальным в классе полиномов первого порядка P(a₁;z),zD, причём

. (2.2)

Доказательство.

Пусть . Так как в этом случае

то в силу принципа максимума модуля аналитической функции на границе круга D выражение

Ясно, что минимум данного выражения по б при фиксированном достигается при , т.е.

.

А так как минимум по h достигается при h=R^-1, то окончательно получаем (1.2).

Пусть теперь D представляет собой объединение двух кругов

, где

Теорема 1.3

Пусть Ш и . Тогда классе полиномов P(a₁;z), zD экстремальным будет полином P(a^*₁;z) с , где

а является решением уравнения

. (2.4)

При этом

(2.5)

Доказательство.

Применяя неравенство (1.3), получаем

(2.6)

При фиксированном h>0 значение каждого из выражений (2.6) определяется величиной , . Нетрудно показать, что

достигается при выполнении условия (1.4). Таким образом, при фиксированном h>0

Точку h_*, в которой достигается минимум функции g(h), найдём, приравнивая производную к нулю:

Решая относительно h уравнение

Получаем



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

то есть справедливо равенство (2.5).

Теорема 1.4

Пусть спектр линейного ограниченного оператора A:EE расположен в объединении двух кругов, удовлетворяющих условиям теоремы 1.3.

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

, (2.7)

где --некоторая положительная константа.

Доказательство.

Заметим, что при выполнении условий теоремы

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

Оценка (2.7) скорости сходимости приближений {x_k} к решению вытекает из возможности построения в пространстве E нормы , эквивалентной исходной и в которой норма оператора А не будет превосходить величины .

3. Итерационные методы второго порядка

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

,

необходимо и достаточно, чтобы

Ш,

где

--аннулятор G, а --субдифференциал функции f. Этим критерием нам будет удобнее воспользоваться в следующей редакции: является элементом наилчшего приближения тогда и только тогда, когда

В дальнейшем данное утверждение будем называть критерием Иоффе-Тихомирова.

Предположим, что областью определения D полинома второго порядка

является прямоугольник с вершинами в точках

.

Точку a+hi обозначим z₃. Всюду в дальнейшем предполагается выполненным условие

(2.8)

Условие (1.8) обеспечивает выполнение неравенства

(2.9)

где --экстремальный полином в классе полиномов .

4. Некоторые итерационные методы и их оптимизация

4.1 Простейший итерационный метод

Пусть матрица А системы

(4.1)

симметрична, положительно определена и известны границы ее спектра в=в(A)? Для решения этой системы применим итерационный метод

(4.2)

с некоторым начальным вектором и вещественным параметром . [2, c. 165]

Для векторов ошибок этого метода выполняется соотношение

(4.3)

где

(4.4)

-- оператор шага.

Обозначим через множество собственных чисел А, а через -- полную ортонормированнyю систему соответствующих собственных векторов А. Тогда, разлагая векторы {} по ортонормированному базису :

,

и используя (2.3), получим

.

Отсюда следует, что для сходимости к нулю коэффициентов при и любом необходимо и достаточно выполнение неравенств

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

необходимо и достаточно, чтобы выполнялось неравенство

(4.5)

Исследуем величину q(). Рассматривая систему неравенств

которая эквивалентна неравенству (4.5), приходим к выводу, что (4.5) будет выполняться только в случае

 (4.6)

т. е. при ф. Таким образом, для определения области изменения значений , при которых метод (4.2) сходится, нам достаточно знать либо величину , либо оценку сверху этой величины.

Перейдем к изучению проблемы оптимизации метода (4.2). Используя неравенство

(4.7)

где в силу симметричности Т

, (4.8)

нетрудно видеть, что для уменьшения , в () раз достаточно провести N итераций, где N определяется из уравнения

(4.9)

Отсюда, учитывая (4.8), получим

(4.10)

Так как число арифметических и логических действий на одну итерацию метода (4.2) не зависит от значения , то функционал W из (4.10) в данном случае определяется соотношением

(4.11)

Здесь предполагается, что . Теперь легко видеть, что проблема оптимизации (минимизации W по ) сводится к минимизации по функции q(). Решим эту задачу.

Простейший анализ показывает, что

(4.12)

а оптимальное значение является решением уравнения

и вычисляется по формуле

(4.13)

Подставляя это значение в (2.12), получим

(4.14)

где величина

(4.15)

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

Введем дополнительно величину

, (4.16)

которую будем называть асимптотической скоростью сходимости метода (4.2). Очевидно, что равно числу итераций, достаточных, а при произвольном также необходимых для уменьшения в раз, где =2,7... -- основание натуральных логарифмов. Асимптотическая скорость сходимости оказывается удобным критерием для сравнения различных методов, когда вопрос о числе арифметических и логических действий на итерацию не обсуждается. С учетом введенной величины (4.11) принимает вид

(4.17)

В заключение остановимся на случае плохо обусловленных матриц, т. е. когда р>>1. Учитывая, что при р>>1

(4.18)

Получаем

(4.19)

и, следовательно,

(4.20)

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

4.2 Сходимость и оптимизация стационарных итерационных методов

В предыдущем пункте было показано, что необходимым и достаточным условием сходимости итерационного метода (4.2) для любого начального приближения ° является выполнение неравенства

(4.21)

где -- собственные числа оператора шага Т. Сейчас мы докажем, что выполнение неравенства (2.21) является необходимым и достаточным условием сходимости стационарного метода

с оператором шага

Т=Е-НА,

являющимся постоянной матрицей.

Пусть

-- нормальная жорданова форма матрицы Т (т. е. , где столбцами матрицы 5 являются собственные и корневые векторы матрицы Т) с клетками Жордана



порядка , которые соответствуют собственным числам Тогда, так как

где {} -- векторы ошибок, нетрудно видеть, что необходимым и достаточным условием сходимости стационарного итерационного метода является сходимость матриц (и, следовательно, матриц Jⁱ) к нулевой матрице при . Последнее выполняется только в том случае, если для любого i () матрицы Jⁱ_i сходятся к нулевой матрице при .

Таким образом, для доказательства сформулированного утверждения о необходимом и достаточном условии сходимости стационарного итерационного метода нам достаточно показать, что матрицы Jⁱ_i сходятся к нулевым матрицам при только в случае <1. Обозначим через элементы матрицы Jⁱ_i.

Тогда путем непосредственного перемножения матриц нетрудно показать, что

Где

суть биномиальные коэффициенты. Иначе говоря,

для всех и . С помощью элементарных выкладок легко показать, что стремятся к нулю для всех , при (соответственно сходятся к нулевой матрице) только в случае <1. Утверждение доказано. Известно, что этот результат справедлив для любого стационарного итерационного метода.

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

Для любой квадратной матрицы Т и любой матричной нормы выполняется равенство

(4.22)

Предположим теперь, что матрица стационарного итерационного метода

 (4.23)

зависит от параметров . Тогда, если независимо от значений параметров каждая итерация метода требует одного и того же числа арифметических и логических действий , то, согласно предыдущему (см. 2.1), проблема оптимизации метода (4.23) заключается в минимизации по функции

(4.24)

где --число итераций, достаточных для уменьшения некоторой нормы вектора ошибки в 1/ раз. Так как

(4.25)

где , а -- некоторая норма, то уравнение для определения зависимости N от и е имеет вид

(4.26)

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

Одним из возможных путей приближенного отыскания зависимости N от и является асимптотический подход; именно, если предположить, что и, соответственно, N1, то из сформулированной выше теоремы будет следовать, что

(4.27)

где -- асимптотическая скорость сходимости (4.23). Таким образом, функцию W можно определить соотношением

(4.28)

Заметим, что (4.17) является частным случаем (4.28).

Из полученной формулы (4.28) следует, что при сделанных предположениях проблема оптимизации метода (4.23) заключается в максимизации R() (минимизации ) по тем параметрам , для которых <1.

Остановимся кратко на циклических итерационных методах с периодом . Как уже было показано в 1, циклический итерационный метод может быть приведен к обычному стационарному итерационному методу (4.7) с оператором шага

(4.29)

Предполагая, что каждая итерация метода требует sW₀ арифметических и логических действий, где -- аналогичная величина для одного шага циклического метода, получим

(4.30)

Отсюда следует, что в случае циклических итерационных методов оптимизация этих методов при фиксированном s заключается в минимизации величины .

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

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

(4.31)

с блочно-трехдиагоиальной матрицей

(4.32)

где -- единичные матрицы порядка , a и -- некоторые матрицы порядка и соответственно. Отметим, что системы с матрицами такого вида часто возникают при редукции уравнений эллиптического типа к системам конечно-разностных или вариационно-разностных уравнений.

Представим матрицу А в виде

A=E-R-S, (4.33)

где

и Е -- единичная матрица. Тогда, если ввести матрицу

B = R + S (4.34)

систему (4.31) можно записать в виде

= В +f (4.35)

Далее мы везде будем предполагать, что итерационный метод

(4.36)

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

Перепишем (2.31) в виде системы матричных уравнений

(4.37)

при условиях

и

где Ф_l и F_l -- векторные компоненты векторов и . Тогда метод последовательной верхней релаксации определяется формулами

(4.38)

где -- некоторый вещественный параметр. Соотношения (4.38) можно также записать в виде

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

Перейдем от (4.38) к уравнениям для векторов ошибок , где {Ф_l*}--решение системы (4.37):

(4.39)

Отсюда видно, что оператор шага метода (4.37) определяется равенством

(4.40)

и зависит от одного параметра , а спектральная задача

(4.41)

легко преобразуется к виду

 (4.42)

Решение этой спектральной задачи будем искать в виде

(4.43)

где -- векторные компоненты собственного вектора щ спектральной задачи

(4.44)

а . Подставляя (4.43) в (4.42) и учитывая (4.44), получим

(4.45)

Так как нулевые значения с точки зрения сходимости метода последовательной верхней релаксации нас не интересуют, а среди {щ_l}есть хотя бы один ненулевой вектор, то из (4.45) получаем уравнение

которое связывает собственные числа матриц и В. Решив это уравнение, получим

(4.46)

Прежде чем переходить к анализу этой формулы, заметим, что если (В) -- собственное число матрицы В, то величина -- (В) также является собственным числом матрицы В. Действительно, если (В)щ = Bщ, где w -- собственный вектор матрицы В с векторными компонентами , то вектор с векторными компонентами является собственным вектором В, соответствующим ее собственному числу--(В), т.е.

(4.47)

Из доказанного и формулы (4.46) следует, что при анализе нам достаточно ограничиться случаем (В).

Исследуем величину , как функцию параметра , считая, что (В) < 1 -- некоторое фиксированное неотрицательное собственное число матрицы В. Сначала рассмотрим случай . Как показывают несложные вычисления, при неравенство

(4.48)

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

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

где при положительности подкоренного выражения значение квадратного корня берется положительным.

Далее, для значений , где

подкоренное выражение в (2.48) неположительно и для этих значений имеем

Если же , то подкоренное выражение в (4.48) всегда положительно, а неотрицательно. Учитывая это, нетрудно показать, что при неравенство не имеет решения, а при выполняется неравенство

Из доказанных фактов вытекает следующее утверждение: при сделанных выше предположениях условие необходимо и достаточно для сходимости метода последовательной верхней релаксации (4.38).

Остановимся теперь на исследовании величины

как функции параметра . Так как для значений т. е. получаем



и = 1 при = 0, то график для различных (В) имеет следующий вид:

Рисунок 4.1-- График для различных (В)

Поскольку

то для значений

Из последней формулы сразу следует, что минимальное значение достигается при =₁. Таким образом, значение _опт, максимизирующее асимптотическую скорость сходимости метода последовательней верхней релаксации, вычисляется по формуле

(4.49)

Причем

(4.50)

Проанализируем теперь формулы (4.49), (4.50) в случае плохо обусловленных матриц (предполагая дополнительно, что матрица А симметрична), т. е. когда . Так как одновременно с (В) собственным числом матрицы В вида (4.34) является величина --(В) (это доказано ранее), то из соотношения В = Е -- А вытекает, что

Отсюда следует, что , а условие p(A)>1означает выполнение соотношений

Подставляя эти значения в (4.49), (4.50), асимптотически получим

. (4.51)

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

4.4 Чебышевский итерационный метод

Рассмотрим систему линейных алгебраических уравнений

(4.52)

с симметричной и положительно определенной матрицей А. Для решения этой системы предложим итерационный метод

(4.53)

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

Циклический итерационный метод (4.53) с длиной цикла sl может быть описан (см. 1) как стационарный итерационный метод вида

(4.54)

с оператором шага

Так как матрица А симметрична, то

и, согласно результатам 4.2, оптимизация метода (4.53) сводится к минимизации по параметрам ₁,..., _s. В случае s=l точное решение этой задачи было дано в 4.1. В случае же s>l точное решение задачи невозможно, так как простого знания границ спектра А для этого недостаточно, а определение всех собственных чисел A--более сложная задача, чем решение системы (4.52) простейшим итерационным методом. Поэтому с целью оптимизации метода осуществляют минимизацию функции

где , которая мажорирует сверху величину и достаточно хорошо ее приближает на практике.

Наряду с задачей минимизации q_s() рассмотрим задачу построения многочлена степени s, являющегося решением задачи

где Q_s -- множество всех степени s, удовлетворяющих условию P_s(0)= 1.

Решение последней задачи было дано А. А. Марковым с помощью многочленов Чебышева:

(4.59)

где

r_s -- некоторая константа. Отсюда получаем

При этом



Вернемся теперь к проблеме оптимизации метода (4.53), т. е. к решению экстремальной задачи

где обозначает последовательность параметров ₁,..., _s. Если обозначить через V_s множество многочленов P_s () степени s вида

то задача (2.63) может быть сформулирована следующим образом: найти многочлен P_s(), являющийся решением задачи

Так как V_s Q_s, то очевидно, что

Поскольку решением задачи (4.58) является многочлен вида (4.64), т. е. принадлежащий V_s, то в (4.66) выполняется строгое равенство. Учитывая это, приходим к выводу, что в качестве может быть выбран многочлен Окончательно отметим, что выбор

= (4.67)

единствен, так как единственно решение задачи (4.58).

Если, где и при , обозначить целочисленную перестановку порядка s, то из (4.62) следует, что для оптимального итерационного метода (4.54)

(4.68)

где

а х_i --корни многочлена T_s(x). Итерационный метод (4.54) с выбранными по формуле (4.68) параметрами мы будем называть чебышевским итерационным методом.

Оценим теперь скорость сходимости чебышевского итерационного метода. Покажем, что значение длины цикла s может быть выбрано из условия, чтобы s итераций метода (4.53) (одна итерация по методу (4.54)) обеспечивали уменьшение начальной ошибки в 1/ раз. Рассмотрим уравнение

Если ввести обозначения

и использовать соотношение

то после несложных преобразований имеем

Рассматривая последнее соотношение как квадратное уравнение относительно и учитывая, что <1, получим

и, следовательно,

В случае и это выражение принимает вид

откуда следуют соотношения

(4.69)

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

Как следует из изложенного, для реализации чебышевского итерационного метода нам необходимо знать границы б и спектра матрицы А. Эта проблема весьма актуальна, поскольку для значений х[--1, 1] наблюдается быстрый рост многочленов Чебышева и, следовательно, ошибка в определении границ спектра может привести к очень медленной сходимости процесса.

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

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

5. Нестационарные итерационные методы

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

5.1 Теоремы сходимости

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

(5.1)

и квадратичный функционал

(5.2)

где ц*=A¹f -- точное решение системы (3.1), a D -- симметричная положительно определенная матрица.

Так как J(ц)>0 для любого ц?ц* и J(ц*) = 0, то задача решения системы (5.1) эквивалентна задаче минимизации функционала (5.2), т. е. нахождения вектора ц*, минимизирующего J(ц). Если D = А*А, то функционал

J(ц)=(Aц-f,Aц-f)=||Aц-f||₂² (5.3)

называется функционалом квадрата невязки.

Если предположить, что A-- симметричная положительно определенная матрица и D = A, то

J (ц)=J₁(ц)+(Aц^*, ц^*),

где

J₁(ц)=(Aц, ц)-2(ц,f). (5.4)

Таким образом, J (ц) с точностью до константы (Aц^*, ц^*)=(f, ц^*) совпадает с известным вариационным функционалом J₁(ц). Заметим, что функционалы (5.3) и (5.4) не зависят от искомого вектора ц*.

Сделанные замечания позволяют сформулировать новые принципы оптимизации итерационных методов, которые мы назовем вариационными принципами. Рассмотрим итерационный метод

ц^j+1=ц^j-H_ф(A ц^j-f), (5.5)

матрица H_ф которого зависит от параметров ф₁,...,ф_s. Предположим, что для значений ф₁,...,ф_s из некоторого множества Q метод (5.5) сходится, причем последовательность значений {ц^j} осуществляет последовательную минимизацию функционала (5.2). В предыдущем параграфе мы выбирали значения ф₁,...,ф_s из условия минимума спектрального радиуса матрицы шага = E-. В настоящем параграфе будут рассмотрены методы, для которых параметры ф₁,...,ф_s выбираются из условия максимальной минимизации на каждом шаге функционала (5.2).

Так как матрица D положительно определена, то нетрудно

видеть, что соотношение

(5.6)

определяет норму в пространстве векторов ошибок. Соответственно соотношение



определяет норму матрицы В. Введенную норму часто называют D-нормой. Ранее мы предположили, что при (ф₁,...,ф_s) функционал (5.2) с некоторой матрицей D последовательно минимизируется. Это означает, что для любого

(5.8)

Так как для стационарного итерационного метода матрица Т_ф постоянна, то из последнего неравенства следует, что для любого вектора ??^j

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

достигается на некотором векторе z₀. Отсюда и из (5.8) вытекает

(5.9)

Итак, мы показали, что при сделанном предположении (ф₁,...,ф_s)

Сформулируем теперь нестационарный метод, соответствующий методу (5.5):

(5.10)

где и параметры удовлетворяют уравнению

(5.11)

Справедливо следующее утверждение.Если для итерационного метода (5.5) выполнены сделанные выше предположения (т. е. множество Q не пусто), то итерационный метод (5.10), (5.11) сходится, причем

(5.12)

для любого ф=(ф₁,...,ф_s)Q, где -- оператор шага метода (5.10), (5.11).

Для доказательства этого утверждения достаточно показать справедливость неравенства (5.12). Пусть метод (5.5) сходится для значений ф₁,...,ф_s и для этого метода для любого ??^j. Тогда, как показано выше,

.

Далее, так как по определению

то

для любого ??^j и, следовательно,

что и требовалось доказать.

В заключение докажем еще одно утверждение, определив предварительно асимптотическую скорость сходимости нестационарного итерационного метода соотношением

Если при любых ф₁,...,ф_sQ, для которых метод (5.5) сходится, выполняется соотношение

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

Как было показано в 4.2,

С другой стороны,

Отсюда получаем

(5.13)

Так как это неравенство справедливо для любых ф₁,...,ф_sQ, то утверждение доказано.

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

5.2 Метод минимальных невязок

Выберем

D= A*A и H=фE (5.14)

и предположим, что A = A*>0.

В 5.1 было показано, что в этом случае при итерационный метод

(5.15)

сходится. При этом простейший спектральный анализ показывает, что

(5.16)

Рассмотрим соответствующий нестационарный процесс, называемый методом минимальных невязок:

(5.17)

где

(5.18)

( -вектор невязки). Из (5.17) следует, что

Очевидно, что ф_j находится из уравнения

Так как метод (5.15) сходится для , где в=в(А), то, согласно утверждению из 3, метод минимальных невязок сходится, причем

(5.19)

Из соотношения для последовательности норм невязок метода (5.17), (5.18)

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

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

Для ускорения сходимости метода минимальных невязок целесообразно время от времени использовать один шаг двухшагового метода минимальных невязок, формулы которого имеют вид

(5.20)

где ф_j и г_j выбираются как решение системы двух уравнений:

(5.21)

5.3 Метод сопряженных градиентов

Определим в исходном пространстве векторов некоторую D-норму и некоторое подпространство G_s с базисом {g_i}^s_i= i [3, c. 294]. Тогда задача наилучшего приближения решения ц* = A^-1f системы Aц=f на многообразии

формулируется следующим образом. Требуется найти вектор = такой, что

(5.22)

Система уравнений для определения коэффициентов {а_i*} разложения

имеет вид

B

где В =b_ij -- матрица порядка s с элементами

и F = (F₁,...,F_s) --вектор с компонентами

Из предыдущего видно, что наиболее простым (с точки зрения реализации процесса) является случай, когда



где -- символ Кронекера, т. е. когда будет D-ортогональным базисом пространства G_s. Если последнее условие выполнено, то

(5.23)

Достаточным условием осуществимости процесса (5.23) является требование, чтобы вектор D* был известен. Это требование выполняется, например, либо в случае D= A, если A=A*>0, либо в случае D = A*A для произвольной A.

Конкретизируем вариационную задачу (5.22) с целью изучения одного класса методов. Предположим, что подпространство G_s является линейной оболочкой системы линейно независимых векторов

а матрица А симметрична и положительно определена. Как уже было указано выше, если в заданном подпространстве G_s мы сможем найти некоторый A-ортогональный базис {g_i}^s_i=1 то искомое приближение к вектору * найдется по формулам

(5.24)

Этот процесс можно записать еще следующим образом:



(5.25)

где -- вектор невязки и . Наиболее известным способом построения базиса в пространствах типа G_s является процесс Шмидта. Однако для матриц A высокого порядка он требует большого числа арифметических действий и большой памяти ЭВМ при численной реализации. Для случая симметричных, но не положительно определенных матриц эффективным способом построения A²-ортогонального базиса (т. е. когда D=А²) в пространстве G_s является метод минимальных итераций Ланцоша. Самым экономичным из известных способов A-ортогонализации векторов для симметричных и положительно определенных матриц является метод сопряженных градиентов, формулы которого имеют вид

(5.26)

где --векторы невязки.

Докажем, что построенные по этим формулам векторы g_k}^s_{k = l} образуют А-ортогональный базис пространства G_s, если векторы линейно независимы. Сначала покажем, что все векторы {g_k}^s_{k = l} будут ненулевыми. В самом деле, если в (5.26) провести последовательное исключение, то легко видеть, что

(5.27)

с некоторыми коэффициентами {в_ki}- Поэтому соотношение g_k = 0 будет противоречить требованию линейной независимости векторов . Теперь остается показать, что векторы {g_k}^s_k=1 A-ортогональны. Предположим, что для некоторого k2 выполняются соотношения (для k=l, 2 их выполнение устанавливается непосредственной проверкой)

(5.28)

и докажем их справедливость на (k+1)-м шаге. Для этого нам понадобятся равенства

(5.29)

(здесь полагается g_o = 0). Чтобы вывести эти соотношения, достаточно воспользоваться равенствами, полученными из (5.26), и условиями

Так как в силу предположений

и по построению (Ag_k+1, g_k) = 0, то

(Ag_k+1,g_j)=0 (5.30)

для всех jk. Далее, поскольку , то по построению и из предположений (5.28) следует, что

(5.31)

для любого ljk+l. Объединяя (3.30) с (3.31) и учитывая неравенство

получаем, что на (k + 1)-м шаге все соотношения (5.28) выполняются. Продолжая по индукции до s-гo шага, приходим к выводу об А-ортогональности системы векторов {g_k}. Таким образом, метод сопряженных градиентов решает вариационную задачу (5.22).

В заключение обсудим случай вырождения, когда для некоторого k система векторов линейно независима, а система линейно зависима, т. е.

(5.32)

с некоторыми коэффициентами , среди которых есть отличные от нуля. Коэффициент С_о отличен от нуля, так как в противном случае, умножая (5.32) на A^-1 получаем

что противоречит линейной независимости системы векторов .

Из (5.32) имеем

что означает: *-Отсюда и из (3.28) следует, что приближение необходимо равно вектору *- ( =). Иначе говоря, в данном случае метод сопряженных градиентов позволяет найти точное решение системы (5.1) уже на k-м шаге.

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

(5.33)

с симметричными и положительно определенными матрицами A и В формулы ускорения с помощью метода сопряженных градиентов имеют следующий вид:

(5.34)

Метод сопряженных градиентов по своей идее (теоретически) является прямым методом, поскольку при s>n, где n -- порядок матрицы A, система векторов всегда линейно зависима, и, следовательно, при некотором s процесс должен заканчиваться получением точного решения. С другой стороны, при реализации метода сопряженных градиентов на ЭВМ в случае матриц высокого порядка, как правило, уже через несколько десятков итераций возникает явление численной неустойчивости процесса ортогонализации и реальный процесс перестает отражать свойства реализуемого метода. В силу отмеченного обстоятельства анализ метода сопряженных градиентов можно проводить как анализ нестационарного итерационного метода с длиной цикла s, т. е. через каждые s шагов по методу сопряженных градиентов начальное приближение выбирается заново. При такой постановке скорость сходимости метода может быть оценена через скорость сходимости циклического чебышевского итерационного метода. Действительно, для любого sl

, (5.35)

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

(5.36)

и использовать оценку (5.12) настоящего параграфа, то приходим к выводу, что s-циклический метод сопряженных градиентов сходится не медленнее s-циклического чебышевского метода и, следовательно, для него справедливы те же самые оценки скорости сходимости. Отметим две важные особенности метода сопряженных градиентов, проявляющиеся при решении конкретных вычислительных задач. Во-первых, реализация одного шага метода сопряженных градиентов требует большее (иногда значительно) число арифметических и логических действий по сравнению с одним шагом чебышевского итерационного метода. Во-вторых, при реализации (особенно на первых итерациях) метод сопряженных градиентов в соответствующей норме значительно быстрее минимизирует A-норму вектора ошибки, чем это показывает оценка. Для иллюстрации отмеченного факта выпишем соотношение, вытекающее из (5.22) для метода сопряженных градиентов (способа определения подпространства G_s):

(5.37)

где -- вектор ошибки на k-м шаге, -- вектор начальной ошибки, а Р_k () -- многочлен степени k от , удовлетворяющий условию P_k(0) = l. Теперь, если положить М=1 (этого всегда можно добиться нормировкой матрицы А) и m = 0 (без ограничения общности), то, полагая

(5.38)

получим для метода сопряженных градиентов оценку

(5.39)

Заметим, что в силу m = 0 оценка (5.39) справедлива и в случае вырожденной матрицы А.

6. Итерационные методы уточнения корней

Рассмотрим самый мощный класс методов уточнения корней уравнений. Его достоинство состоит в том, что основная идея рассматриваемых ниже методов является универсальной при приближенном решении уравнений многих классов. Так называемые итерационные методы уточнения корней уравнений основаны на математической теории, которую необходимо предварительно рассмотреть. [4, c. 195]

6.1 Метрические пространства и принцип сжимающих отображений

Понятие «расстояние» привычно на уровне геометрической наглядности. Легко определить привычным образом расстояние между точками на числовой оси или на координатной плоскости. Однако в математике это понятие используется гораздо шире.

Способ измерения расстояния между элементами х и у некоторого множества X (произвольной природы) называется метрикой. Множество с введенной в нем метрикой становится метрическим пространством, если для любых элементов:

1);

2)тогда и только тогда, когда x совпадает с y;

3);

4)

Последовательность точек метрического пространства называется фундаментальной, если для любого существует такое число N, что для любых номеров точек m иn, для которых m ,n > N, выполняется неравенство .

Рисунок 6.2-- «сжимающее отображение» -- расстояние p(Fx, Fy) меньше расстояния р(х,у)

Метрическое пространство называется полным, если в нем любая фундаментальная последовательность сходится (имеет предел). Примерами полных метрических пространств являются:

1) множество точек на числовой оси, расстояние между которыми определено по формуле .

2) множество точек на координатной плоскости, расстояние между которыми определено по формуле

(здесь -- координаты одной точки, -- другой).

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

Пусть F-- отображение, действующее в метрическом пространстве Е с метрикой ; х и у -- точки пространства Е, a Fx, Fy -- образы этих точек.

Отображение F пространства Е в себя называется сжимающим отображением (рисунок 6.2), если существует такое число , 0<< 1, что для любых двух точек х, у Е выполняется неравенство

(6.1)

Точка х называется неподвижной точкой отображения F, если отображение переводит ее саму в себя: Fx = x.

Важнейшее значение в теории решения уравнений имеет следующая теорема:

Принцип сжимающих отображений. Если F-- сжимающее отображение, определенное в полном метрическом пространстве, то для него существует единственная неподвижная точка такая, которая переводится отображением в себя: . Эта точка является пределом последовательности

(6.2)

с любым начальным членом .

Заметим, что последовательность (6.2) называют итерационной последовательностью (от лат. iteratio -- повторение). Итерационная

последовательность, образуемая сжимающим отображением, является сходящейся.

В процессе доказательства получается оценка расстояния между неподвижной точкой отображения и очередным приближением :

(6.3)

Приняв (k-1)-е приближение за нулевое (k= 1), получаем еще одно полезное для приложений неравенство:

. (6.4)

Здесь -- множитель из условия сжимаемости (6.1)

6.2 Метод простой итерации

Применим принцип сжимающих отображений для уточнения значения корня уравнения

F(x)=0 (6.5)

Для этого заменим это уравнение равносильным уравнением

x=f(x) (6.6)

Сделать это можно множеством способов. Простейший и очевидный -- добавить х к левой и правой частям уравнения (6.5).

Пусть -- корень уравнения (6.6), а х₀ -- полученное каким-либо способом на этапе отделения корней грубое приближение к корню . Подставляя в правую часть уравнения (6.6), получим некоторое число x₁=f(x₀). Проделаем то же самое с х₁ получим x₂ = f(x₁) и т.д. Последовательно применяя рекуррентное соотношение х_n = f(x_n-1) для n= 1, 2, ..., образуем итерационную последовательность, совершенно подобную последовательности (6.2):

...