1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 33

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

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

Сходимость итераций исследуем так же, как для одной переменной. Обозначим компоненты решения через хА и преобразуем погрешность очередной итерации хьо+'1 — е|=<рА(х», ..., х'„') — чъ(х„..., х.) = = |рА (хсо) — |рА (х) = (д<р» ДА)/д!1 р (хо|, х) = Р ~~ ~(х<'| — х;) (дгрь ф„)/дхД, |=| где ! — направление, соединяющее многомерные точки хьн н х, а ~„— некоторая точка, лежащая между ними на этом направлении. Зто равенство означает, что вектор погрешности нового приближения равен матрице производных, умноженной на вектор погрепшости предыдущего приближения.

Если какая-нибудь норма матрицы производных (дя|„Я„)/дк,), согласованная с некоторой нормой вектора, меньше единицы, то норма погрешности убывает от итерации к итерации по геометрической прогрессии. Зто означает линейную сходимость метода. На практике удобней рассматривать матрицу с элементами Мм — — |пах~дсрА/дх;!. Нормы этой матрицы мажорируют соответствующие нормы матрицы производных, поэтому достаточным условием еходимоети является 11 Мм й ( 1. При использовании разных норм матриц это условие принимает такие формы: ~'Мм(1, нли ~ Мм(1, или ~ М1|<1.

(45) Каждая норма матрицы согласована с определенной нормой вектора, но в конечномерном пространстве все нормы эквивалентны. Значит, если итерации сходятся в одной норме, то они сходятся и во всех остальных нормах. Поскольку сходимость линейная, то оканчивать итерации можно по критерию сходимости (26), выполнение которого надо проверять для каждой компоненты. Линейная сходимость довольно медленна; поэтому полезно уточнять результат процессом Эйткена по трем последним итерациям, )йй СИСТЕМЫ УРАВНЕНИИ 1гл. ч Сами вычисления в методе последовательных приближений просты. Но зато сложно найти такую систему х=>р(х), которая была бы эквивалентна исходной системе у(х) = О н одновременно обеспечивала бы сходнмость.

Сходимость метода нередко удается улучшить. В методе простых итераций найденное пРиближение хан+И использУетеЯ только дла вычислениЯ следУю. щей итерации. Можно использовать его уже на данной итерации для вычисления следующих компонент; я~э+ и = гха+ >> ка+ и ха+ и ха> ха> ка>> (4в) Сходимость этого варианта л>етода тоже линейная; детально ее исследовать не будем. При ручных расчетах можно еще ускорить сходимость за счет перестановок отдельных уравнений на основе анализа их невязок гаа> = =хам>->р (хы)=хай> — хам+и; но для расчетов на эВм это неудобно, ибо обычно такой анализ полуинтунтивен и плохо алгоритмизируется. 2.

Метод Ньютона. Пусть известно некоторое приближение хм> к корню х. Как и для одной переменной, запишем исходную систему (43) в видеуа(хы>+Ах) =О, где Лх=х — х". Разлагая эти уравнения в ряды и ограничиваясь первыми дифференциалами, т. е. линеаризуя функцию, получим >акр>= — (ь(хм>), ) =й~п. (47) с-> Это система уравнений, линейных относительно приращений Лха> все коэффициенты этой системы выражаются через последнее приближение х">. Решив эту систему (например, методом исключения), найдем новое приближение хы»>=хсо+Лхпа Как и для одной переменной, метод Ньютона можно формально свести к методу последовательных приближений, положив гр(х)=х — 1дг/дх)-зу(х), где 1дугдх) ' есть матрица, обратная матрице производных.

Аналогично проводится теоретический анализ условий сходимости. Однако достаточное условие сходи- мости, записанное в координатной форме, здесь имеет настолько сложный вид, что проверить его выполнимость почти никогда не удается. Отметим только очевидный результат: в достаточно малой окрестности корня итерации сходятся, если г(е1 (ду>дх1 ~ О, причем сходимоста квадратичная. Следовательно, если нулевое приближение выбрано удачно, то метод Ньютона сходится, причем очень быстро (обычно за 3 — 5 итераций), Поэтому на практике этот метод используют чайде всего. В отличие от метода простых итераций, для метода Ньютона хорошим критерием окончания итераций является условие СИСТЕМЫ НЕЛИНЕИНЫХ УРАВНЕНИИ 431 ~).к(') — х('") ~) =.е. В самом деле, вблизи корня ньютоновские итерации сходятся квадратично, поэтому если этот критерий выполнен, то ) хы'т) — х~)-е' ~ е.

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

Поэтому скорость сходи- мости заметно уменьшается и требуемое число итераций возрастает. 3. Методы спуска. Рассмотрим функцию Ф(х) = У', )(ь(х) )в. а=! Она неотрицательна и обращается в нуль в том и только в том случае, если К(х) =О. Таким образом, решение исходной системы уравнений (43) будет одновременно нулевым минимумом скалярной функции многих переменных Ф(х).

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

Надо помнить, что метод спуска в зависимости от выбора нулевого приближения может сойтись к любому минимуму функции, А функция Ф(х) может иметь ненулевые локальные минимумы, которые не являются решениями исходной системы уравнений. 4. Итерационные методы решения линейных систем иногда дополняют, а иногда заменяют прямые методы. Решая линейную систему (1) общего вида методом исключения, попутно мох<но проверигь, насколько хорошо она обусловлена. Решение, найденное прямым методом, из-за ошибок акруглеяня будет приближенным. Нетрудно проверить, что поправки н нему удовлегворяют уравнениям и ~ ~ аы Лх;=гь, 1 -.

Й =.л, (48) где гь — невязки (7). Это линейная система с той же матрицей, что исходная система (!). Решим ее, нспользун ранее найденные коэффициенты с а (т. е. почти не увеличивая общего объема вычислений). Ранее отмечалось, что в методе Гаусса невязки малы. Если величины Лхг тоже окажутся малымн, то система хорошо обусловлеяа; если большими — то плохо.

В последнем случае зачастую удается уточнить решение, рассматривая (48) как итерационный процесс Ньютона и делая 2 — 3 итерации, 154 СИСТЕМЫ УРАВНЕНИИ Для уточнения обратной матрицы тоже есть итерационный процесс с квад. ратнчной сходимостыо Аэ".ь ! =Аз ~+Аз'Я„Я =Д вЂ” АА,'. (49) Однако каждая итерация этого процесса требует 4п' арифметических действий, т. е. вдвое больше, чем прямое обращенйе матрицы по методам Гаусса или Жордана. Поэтому в практических вычислениях этот процесс теперь не применяют. При очень плохой обусловленности матрицы оба описанных метода уточнения могут потребовать вычислений с двойным и более числом знаков, но тогда лучше применять регулярнзирующие алгоритмы.

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

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

Список файлов книги