POS-KSC (Учебное пособие по численным методам), страница 6
Описание файла
Файл "POS-KSC " внутри архива находится в папке "Учебное пособие по численным методам". Документ из архива "Учебное пособие по численным методам", который расположен в категории "". Всё это находится в предмете "вычислительная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. .
Онлайн просмотр документа "POS-KSC "
Текст 6 страницы из документа "POS-KSC "
Из преобразуемого элемента вычитается произведение элементов, стоящих на побочной диагонали, деленное на ведущий элемент.
5.2.3. Ортогонализация матриц
Матрица называется ортогональной, если , - диагональная матрица, т.е. в ней отличны от нуля только диагональные элементы, если , то - ортонормированная матрица. Любая неособенная матрица может быть представлена в виде: , - ортогональная, а – верхняя треугольная матрица с единичной диагональю.
Рассмотрим матрицу А, как набор вектор – столбцов , - вектора - линейно независимы, т.к. . Выберем первый столбец матрицы - , равным ; .
Запишем , условие ортогональности R позволяет получить :
следовательно, известен и вектор . Аналогичным образом представляется и , где
В общем случае получим выражения:
Покажем, что - элементы матрицы Т. Действительно:
5.2.4. Решение системы уравнений методом ортогонализации
Оптимальной является следующая схема, основанная на свойствах вектора . Запишем систему в виде:
Из структуры векторов следует, что , (i<j).
в уравнении остается одно слагаемое: .
Полученную систему умножим на , находим и вычисляем и т.д.
5.3. Итерационные методы решения СЛАУ
5.3.1. Метод простой итерации
Многие итерационные методы могут быть сведены к процессу простой итерации. При этом исходное уравнение тем или иным способом должно быть сведено к уравнению
Здесь - неизвестный вектор, - заданный вектор правой части, - заданная матрица коэффициентов (оператор). Например, если задана СЛАУ (5.1), то непосредственно принимая
где - единичная матрица, приходим к (5.3.1.1).
Процесс простой итерации строится следующим образом:
В качестве начального приближения можно принять .
Заметим, что переход от (5.1) к (5.3.1.1) может быть выполнен не единственным способом, что приводит к различным модификациям метода простой итерации. Так, метод (5.3.1.3) с преобразованием (5.3.1.2) известен в литературе как метод Ричардсона. Другие методы простой итерации будут рассмотрены в разделе 5.3.2.
Процесс простой итерации может быть эквивалентно записан также в виде ряда по степеням оператора , т.е., в виде, так называемого, ряда Неймана
Если матрица постоянна (не зависит от номера итерации ), то такой итерационный процесс называется стационарным.
Пусть - «гипотетическое» точное решение, строго удовлетворяющее , а - ошибка на -м шаге. Подставляя в формулу простой итерации получаем для соотношения ошибок на и -м шаге . Для нормы ошибки: .
Отсюда следует достаточное условие сходимости процесса простой итерации: .
Действительно, тогда
Оператор с называется сжимающим, а процесс (5.3.1.2), (5.3.1.3) для него сходящимся, т.к. ошибка убывает с каждым шагом, независимо от её начальной величины.
Спектральным радиусом матрицы (конечномерного оператора) называется , где - собственные числа оператора (см. 5.4).
Для любой нормы справедливо соотношение
Доказывается, что необходимым и достаточным условием сходимости процесса простой итерации (5.3.1.3) является
при этом итерации сходятся не хуже геометрической прогрессии со знаменателем .
Условие (5.3.1.5) является, как правило, сильным ограничением при непосредственном применении метода (5.3.1.2), (5.3.1.3) к заданной СЛАУ. Выбор нового оператора с другим спектром при эквивалентности исходной системе (5.1) может значительно расширить область сходимости процесса простой итерации с его участием:
В качестве условия выхода из вычислительного процесса по достижении заданной точности решения , аналогично (3.5.1), можно принять: , где спектральный радиус или какая-либо оценка другой нормы .
5.3.2. Метод Якоби и метод Зейделя
Исторически одними из самых ранних итерационных мето- дов являются метод Якоби и метод Зейделя, которые могут быть представлены в виде модификации метода простой итерации. Перепишем (5.1) в следующем виде
Используем (5.3.2.1) для построения процесса итераций, начиная с при , :
В матричных обозначениях метод Якоби можно записать следующим образом. Представим , где - диагональная матрица, , . - матрица с нулевой главной диагональю. Тогда справедлива запись уравнения аналогично (5.3.1.6), где
.
Матрица - диагональная и , Необходимые и достаточные условия сходимости метода Якоби
Другой известный метод простой итерации для случая, когда строится на основе матрицы с нулевой главной диагональю - это метод Зейделя. Он отличается от метода Якоби тем, что при расчете координат вектора на текущей -й итерации используются не только координаты вектора на предыдущей -й итерации , но и уже ранее найденные на текущей итерации координаты вектора :
В матричных обозначениях это соответствует представлению исходной матрицы как , где -нижняя треугольная матрица, -диагональная матрица, и - верхняя треугольная матрица.
В отличие от метода Якоби действие оператора на вектор предыдущей итерации разделяется здесь на две части:
и процесс его воздействия (но не результат!) нельзя свести к воздействию какой-либо матрицы на вектор предыдущей итерации.
Метод Зейделя хорошо алгоритмизируется. Если известна скорость сходимости метода, нет необходимости хранить оба вектора и .
Достаточными условиями сходимости методов Якоби и Зейделя является диагональное преобладание в матричных элементах:
однако на практике область сходимости значительно шире и определяется условием (5.3.1.5) на спектральный радиус матрицы (5.3.2.3) для метода Якоби и оператора (5.3.2.5) для метода Зейделя. Для решения СЛАУ с ленточными матрицами метод Зейделя является превосходным инструментом. Так, для симметричных положительно определенных матриц он будет всегда сходящимся. Однако возможно улучшение сходимости как метода Зейделя, так и любого другого метода простой итерации с помощью изложенного ниже метода оптимального спектрального параметра.
5.3.3. Метод оптимального спектрального параметра (ОСП) для простой итерации
Рассмотрим случай, когда спектр оператора выходит за границы единичного круга на комплексной -плоскости собственных чисел. В этом случае ряд простой итерации (5.3.1.3) расходится.
Определим выпуклую оболочку спектра оператора как выпуклую замкнутую кривую наименьшей меры, полностью охватывающую спектр оператора на -плоскости. Доказывается, что если точка находится вне выпуклой оболочки спектра, то можно построить сходящийся ряд простой итерации с новым
Рис.1
оператором . Дадим конструктивный способ построения такого сходящегося ряда. Примем:
где - комплексный параметр. При исходные уравнения (5.3.1.1) с операторами и эквивалентны. Выбором попробуем добиться сходимости ряда (5.3.1.6).
Пусть - один из множества кругов радиуса , полностью охватывающих спектр оператора , и пусть при этом точка (Рис.1). Очевидно, что включает в себя выпуклую оболочку спектра. Вектор из начала в центр этого круга обозначим . При дробно-линейном преобразовании (5.3.3.1) с круг переходит в круг с центром в точке и радиусом . Если , то ряд (5.3.1.6) сходится.
Найдем минимум значения . Пусть круг «виден» из точки под углом . Пусть вектор из центра круга в точку касания луча из т.1 и круга. Из рис. 1 очевидно, что и, следовательно, .
Таким образом, если такой круг, что точка и «видимый» из точки под наименьшим углом , то комплексное расстояние до центра этого круга есть оптимальный параметр для сходимости (5.3.1.6), а скорость сходимости ряда (5.3.1.6) не хуже, чем у геометрической прогрессии со знаменателем .
Пусть для спектра известны оценки для , -минимального и максимального по модулю собственного числа (или нижней и верхней границы расстояния от т.0 до области расположения спектра в случае непрерывного спектрального множества). Тогда, если весь спектр оператора размещается в круге , натянутом на точки , как на концевые точки диаметра и точка , для оптимального параметра верна простая приближенная формула
Если граница круга принадлежит спектру, то формула (5.3.3.2) точная. Точная она также и в случае вещественного спектра. Формулу (5.3.3.2) можно улучшить, учитывая более точную конфигурацию спектральной области, например, если область расположения спектра – прямая линия. С помощью формулы (5.3.3.2) во многих случаях можно найти значение близкое к оптимальному параметру в условиях неполного знания свойств спектра, но при известных минимальных и максимальных по модулю собственных числах.
Сходимость каждого из рассмотренных методов простой итерации зависит от конкретного вида исходной матрицы, а точнее, от свойств её спектра. Можно привести примеры матриц, для которых сходится только один из рассмотренных методов, однако комбинация метода простой итерации, Зейделя или Якоби с методом оптимального спектрального параметра (ОСП) позволяют добиться сходимости в случаях, когда каждый из этих методов по отдельности расходится.
Рассмотрим применение метода ОСП на примерах конкретных матричных задач.