Вариационные итерационные методы



Скачать 64.92 Kb.
Дата25.11.2012
Размер64.92 Kb.
ТипЛекция
Лекция 7

23 октября 2006 года.


    1. Вариационные итерационные методы

      1. Связь между вариационной задачей и задачей решения СЛАУ.

Пусть , где Ln есть n-мерное евклидово пространство. Рассмотрим квадратичный функционал от u, называемый функционалом энергии:



где А — линейный оператор, , с — константа. Этот функционал совпадает с квадратичным функционалом где А* — сопряженный к А оператор. Действительно, по определению сопряженного оператора и (uA*u) = (A*uu) в силу коммутативности скалярного произведения. Тогда

так как

Без ограничения общности предположим, что оператор А самосопряженный, А = А*. В противном случае будем рассматривать задачу с оператором при решении вариационной задачи.

Будем также считать, что А — положительный оператор, т.е. A > 0, это означает, что для любого ненулевого вектора u выполнено (Au, u) > 0. Поставим задачу об отыскании элемента v, придающего наименьшее значение функционалу Ф(u):

.

Теорема Пусть А = А* > 0. В этом случае существует единственный элемент , придающий наименьшее значение квадратичному функционалу , являющийся решением СЛАУ Аu f.


Доказательство. СЛАУ Au = f имеет единственное решение v, поскольку А является невырожденным оператором в силу его положительной определенности. Покажем, что в этом случае при для любого вектора Δ имеет место: т.е. при gif" name="object14" align=absmiddle width=39 height=18> достигается минимум квадратичного функционала .

Действительно,











т.е. при и любом имеет место. Докажем, что верно и обратное утверждение. Если элемент доставляет минимальное значение функционалу энергии, то он является решением системы линейных уравнений Из курса математического анализа известно, что в точке минимума должно выполняться условие A > 0. Вычисляя градиент, приходим к условию минимума функционала Таким образом установлена эквивалентность вариационной задачи (отыскание элемента, придающего минимум Ф(u)) и задачи о нахождении решения СЛАУ.

Заметим, что СЛАУ с самосопряженным и положительно определенным оператором А представляют собой важный класс задач в математической физике, в частности, они возникают при решении краевых задач для эллиптических уравнений. При необходимости можно произвести симметризацию по Гауссу исходной системы.

      1. Методы градиентного и наискорейшего спуска

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

(2.25)

, (2.26)

где А — положительно определенная симметричная матрица; αk — параметр, определяемый из заданных условий; например, из условия минимума величины



В этом случае итерационный метод называется методом наискорейшего спуска.

Так как то (2.26) приобретает вид

где (2.27)

что соответствует записи итерационного метода в форме (2.17). Здесь τk является итерационным параметром, который в методе наискорейшего спуска определяется из условия минимума функции по τk. Найдем условие этого минимума.





Здесь учтено соотношение: , поскольку и в силу коммутативности оператора А. Подставим в последние равенства из (2.27), получим откуда следует



, или где

Вектор rk называют вектором невязки.

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

Этот итерационный метод определяется следующим образом. Пусть

как и ранее, Итерационный параметр τk на каждой итерации выбирается так, чтобы минимизировать, евклидову норму невязки . Заметим, что итерационный процесс может быть представлен в равносильном виде в терминах невязки . Тогда для квадрата евклидовой (третьей) нормы невязки получаем условие



Для отыскания минимума невязки на следующей итерации приравняем нулю производную последнего выражения по итерационному параметру τk. Получим равенство

.

Из последнего соотношения находим значение итерационного параметра

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

Этот метод применяется для решения систем уравнений с самосопряженной положительной матрицей А = А* > 0.

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

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

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

Построим такое приближение, чтобы учитывались две предыдущие — трехслойный итерационный метод. Фактически, при построении его применяется процесс ортогонализации Грамма – Шмидта.

Если , то — A-сопряженные невязки.

Имеем метод сопряженных градиентов.

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

Приведем последовательность расчетных формул одного из вариантов метода сопряженных градиентов.





(2.29)

где





В вычислительной практике этот метод используется при умеренном числе обусловленности, больших n и неизвестных границах спектра матрицы А, как итерационный метод, поскольку k0 обычно достаточно большое число. Подробнее о методах сопряженных градиентов можно прочитать в [2].

2.7 О спектральных задачах


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

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



Легко показать, что выражение



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

Для решения полной самосопряженной проблемы собственных значений применяется метод вращений.

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



матрица Λ — диагональная.

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

где матрица Tij есть матрица поворота в плоскости ui uj на угол α. Эта матрица отличается от матрицы A только двумя строками и двумя столбцами (с номерами i и j). Так как евклидова норма матрицы не изменяется при ортогональных преобразованиях, то легко получить соотношение между суммами квадратов внедиагональных элементов старой и новой матриц:



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

Независимо от наличия кратных собственных значений метод вращений обладает квадратичной сходимостью.

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

Похожие:

Вариационные итерационные методы iconПрограмма дисциплины «Вариационные методы в механике деформируемого твердого тела»
«Вариационные методы в механике деформируемого твердого тела» для студентов специальности 1-31 03 02
Вариационные итерационные методы icon1. 10 Численные методы решения нелинейных алгебраических уравнений и систем. Итерационные методы, линеаризация по Ньютону, методы спуска
Корень функции – это такое значение ее аргумента, при котором функция равна нулю
Вариационные итерационные методы iconРазличные методы ориентированы на решение разных классов систем
Как правило, это делается произвольно, хотя от этого очень много зависит. Кроме того, итерационные методы можно проклассифицировать...
Вариационные итерационные методы iconFaq: Численные Методы, часть II системы линейных алгебраических уравнений: итерационные методы
Итерационный метод называется одношаговым, если на каждой итерации требуется результат лишь одной предыдущей итерации. Каноническая...
Вариационные итерационные методы iconП., Щеглов И. А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: итерационные методы
Делоне и методы исчерпывания. Приведены варианты алгоритмов для каждого из указанных методов. Обсуждены особенности построения сеток...
Вариационные итерационные методы iconИтерационные методы оптимизации функций одной переменной Методы деления интервала
Методами поиска определяется достаточно малый интервал, в котором находится минимум, осуществляя при этом наименьшее количество вычислений...
Вариационные итерационные методы iconИтерационные методы решения систем линейных уравнений
Сходимость итерационных методов зависит от свойств матрицы системы и выбора начальных приближений
Вариационные итерационные методы iconВычислительный эксперимент и обработка данных
...
Вариационные итерационные методы iconЛабораторная работа №2 «Численное решение систем линейных уравнений методом простых итераций и методом Зейделя»
Изучить итерационные методы решения слау
Вариационные итерационные методы iconЛекции час. Лабораторные занятия, час. Самостоятельная и инд работа, час Итого часов по теме
Задачи линейной алгебры. Прямые и итерационные методы решения систем линейных алгебраических уравнений
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org