Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (doc) (1113731), страница 3

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

Текст из файла (страница 3)

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

В данном случае определитель матрицы отличен от нуля

,

т. е. обе системы невырожденные. Система 58 отличается от системы 57 возмущением правой части

, , , , .

Решения систем 57 и 58 имеют вид:

, , , , .

При этом

, . 5959\* MERGEFORMAT ()

Мы видим, что небольшое относительное возмущение правой части привело к сильному возмущению решения: относительная погрешность решения равна единице. Этот результат означает, что исходная система плохо обусловлена. Чтобы убедиться в этом, подсчитаем число обусловленности матрицы , напишем с его помощью теоретическую оценку 55 и сравним ее с фактическим результатом 59.

Выпишем линейное преобразование отвечающее матрице системы

при этом

.

Наложим ограничение

,

тогда в силу 44

, .

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

,

зависящего только от одной переменной .

Переходя к тригонометрическим функциям двойного угла

, , ,

сведем подрадикальное выражение к виду:

Для комбинации

, ,

где

, , ,

максимальное значение равно

.

Следовательно

.

С приемлемой точностью это число равно : .

Аналогичным образом находится норма обратной матрицы

, .

Таким образом, в данном примере

. 6060\* MERGEFORMAT ()

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

Она согласуется с результатом 59, который мы получили, непосредственно решая системы 57 и 58.

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

1. Оценка числа обусловленности.

Для числа обусловленности матрицы справедливо неравенство

, 6161\* MERGEFORMAT ()

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

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

,

тогда

,

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

.

Аналогичным образом для собственного вектора _, связанного с , имеем

или

.

Отсюда следует оценка

.

Перемножая два последних неравенства, придем к утверждению 61.

Если матрица симметричная , то все её характеристические значения вещественны, причем

и ,

поэтому для таких матриц

. 6262\* MERGEFORMAT ()

Из полученной оценки для следуют два важных вывода:

1) ;

2) Число обусловленности тем больше, чем больше разброс характеристических чисел матрицы. Поэтому с увеличением размера матрицы, вообще говоря, её обусловленность имеет тенденцию к ухудшению.

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

,

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

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

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

   1. Построение итерационных последовательностей.

Мы видели, что процедура решения СЛАУ

6363\* MERGEFORMAT ()

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

Этого недостатка лишены итерационные методы решения СЛАУ. При их применении ответ получается в процессе построения последовательных приближений (итераций) , сходящихся к решению системы 63 в пространстве с евклидовой нормой

6464\* MERGEFORMAT ()

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

. 6565\* MERGEFORMAT ()

Необходимым и достаточным условием предельного равенства 65 в конечномерном евклидовом пространстве является покомпонентная сходимость:

, .

Сходимость обеспечивает принципиальную возможность получить в процессе итераций ответ с любой наперед заданной степенью точности.

С итерационными последовательностями вы встречались. Каждый следующий член такой последовательности выражается через предыдущие, уже известные. Если, например, формула для вычисления очередного члена последовательности имеет вид:

,

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

.

Такие итерационные алгоритмы называют одношаговыми.

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

, , . 6666\* MERGEFORMAT ()

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

Перепишем формулу 66 в виде

, 6767\* MERGEFORMAT ()

где

. 6868\* MERGEFORMAT ()

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

Наиболее прост в реализации итерационный процесс с единичной матрицей: . В этом случае формулы 67, 68 дают явное выражение очередной итерации через предыдущую:

. 6969\* MERGEFORMAT ()

Из неявных итерационных методов выделим сравнительно легко реализуемые методы с диагональными матрицами: и верхними или нижними треугольными матрицами: .

1. Проблема сходимости итерационного процесса.

Итерационный процесс может быть использован для решения СЛАУ только при условии сходимости. Для исследования его сходимости введем две характеристики. Первая из них – погрешность решения:

. 7070\* MERGEFORMAT ()

Смысл этого вектора ясен. Сходимость итерационного процесса согласно 64 и 65 означает, что

, , . 7171\* MERGEFORMAT ()

Вторая характеристика – невязка:

. 7272\* MERGEFORMAT ()

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

Установим связь между и :

. 7373\* MERGEFORMAT ()

Можно также написать обратное соотношение:

. 7474\* MERGEFORMAT ()

Из формул 73 и 74 вытекают оценки:

, . 7575\* MERGEFORMAT ()

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

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

, . 7676\* MERGEFORMAT ()

В частности,

, .

Преобразование называется самосопряженным, если

, . 7777\* MERGEFORMAT ()

Матрицы сопряженных преобразований в ортонормированном базисе связаны простым транспонированием:

, .

Характеристики

Список файлов лекций