Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 2
Текст из файла (страница 2)
Каждый параграф посвящен одной из таких задач. Принят следующий способ изложения. Вначале дается замкнутая математическая формулировка задачи, указывается ее «прикладное происхождение»». Физическая терминология используется для «оживления» изложения, но никакого физического обоснования постановки задачи не проводится — это дело физика, а не вычислителя. При этом указываются те особые обсгоятельсгва, которые делают задачу нестандартной, требующей разработки специальных вычислительных методов.
Затем описывается метод приближенного решения, оказавшийся достаточно эффективным. Основное внимание уделяется именно тем деталям метода, которые учитывают специфическую нестандартность данной задачи и которым метод обязан своей эффективностью. Попутно обсуждаются те трудности, с которыми сталкиваются прн стандартном подходе к задаче (формально не только возможном, но иногда даже строго обоснованном). В некоторых случаях приводятся и обсуждаются характерные численные результаты. Стандартные детали вычислительной методики описываются бегло, а иногда и совсем опускаются. Материал второй части книги несет двойную нагрузку.
Во-первых, описываемые задачи достаточно интересны в приложениях и опыт нх успешного решения представляет прямой интерес в связи с задачами именно этого типа. Во-вторых, разработка эффективного ПРЕДИСЛОВИЕ алгоритма частной задачи обычно связана с использованием приемов, имеющих более широкое, выходящее за рамки данной задачи значение. Автор предпочитает знакомить читателя с такими приемами на примерах конкретных задач, в которых они были использованы с большим эффектом. Есть и другой путь — выделить эти приемы как отдельные самостоятельные сюжеты, дать абстрактное описание ситуаций, в которых их применение целесообразно. Подобный способ изложения представляется нам чуждым духу вычислительной физики.
Отметим некоторые технические детали изложения. Текст книги разбит на параграфы, каждый из которых имеет свою нумерацию формул. При ссылке на формулы другого параграфа используется двойной номер (параграфа и формулы). Впрочем, автор стремился свести к минимуму подобные ссылки. В тексте опускаются и библиографические ссылки. Этот недостаток компенсируется библиографическим комментарием, тем более необходимым, что во многих местах излагаются результаты, еще не вошедшие прочно в учебную литературу и часто освещенные лишь в журнальных, а то и ротапринтных публикациях. Курсивом в тексте выделены общеупотребительные термины вычислительной математики.
Оба курса, на основе которых написана эта книга, читались по предложению академика О. М. Белоцерковского, много сделавшего для внедрения компьютерных наук в «систему физтеха». Пользуюсь случаем высказать Олегу Михайловичу свою искреннюю благодарность. Автор должен отметить и неоценимое влияние, оказанное на него коллегами по Институту прикладной математики им, М. В. Келдыша. Нет возможности упоминать их здесь, автор постарался должным образом отметить их вклад в развитие предмета книги в библиографическом комментарии к списку литературы.
Это будет полезно и для будущих историков науки, которым рано или поздно предстоит изучать историю становления отечественной вычислительной математики. ЧАСТЬ ПЕРВАЯ ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ В 1. Решение систем нелинейных уравнений В самых различных задачах вычислительной физики часто возникает необходимость решать системы нелинейных уравнений. Такую систему будем записывать кратко в виде у(х) = О, имея в виду, что х есть точка л-мерного пространства, т.е. х = = (х„хм ..., х„), а у — л-мерная вектор-функция, т.е. = У,, ~з, ..., Я. Таким образом, (1) есть система л уравнений с л неизвестными: /~(хп хм ..., х ) =О, (2) Т'„(х,, х, ..., х„) = О.
Конечно, когда речь идет о нелинейных уравнениях в общем случае, мы не имеем ни теорем о существовании, ни теорем о единственности решения. Тем не менее, имея дело с системой (1), мы предполагаем, что искомое решение существует. Оно, быть может, не единственно, н методы, которые будут рассмотрены ниже, не имеют целью найти все решения; обычно достаточно будет какогото одного. Более того, мы предполагаем, что из каких-то содержательных соображений нам известно примерное расположение этого решения, некоторая не очень большая область, в которой оно находится.
Таким образом, лучше говорить не о решении системы нелинейных уравнений, а об уточнении имеющегося весьма грубого приближения к некоторому решению. Ниже это будет должным абразом конкретизировано. Метод Ньютона. Основная вычислительная конструкция, применяемая для решения системы (1), по традиции приписывается Ньютону, хотя теоретические исследования этого алгоритма были выполнены лет на сто позже (Фурье, Коши). Основу метода состав- |о ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ лает фундаментальная для вычислительной математики конструкция — метод итераций (последовательных приближений) и линеаризация уравнений. В методе Ньютона, начиная с некоторого начального приближения хО, последовательно находится точки х', хз, ..., х", ...
таким образом, что 11ш Г(хе) = О, а 1нп х« = х", где х* — решение систе- В мы (1). Нужно только иметь в виду, что вычислительную математику интересует не только факт сходимости, но и скорость скодимости. Метод Ньютона особенно ценен тем, что обеспечивает очень высокую, как говорят, «квадратичную» скорость сходимости (точный смысл этого термина выяснится позже, после доказательства соответствующей теоремы) . Рассмотрим стандартный шаг итерационного процесса метода Ньютона. Пусть имеется некоторое уже найденное приближение х«; следуюгдее приближение хе+' ищем в виде х"«' = х'+ Ьх, где Ьх — малая поправка, уточняющая х«.
Для ее определения выпишем уравнение /(х" + Ьх) = О. Само по себе оно не проще исходного уравнения (1 ), но, используя предположение о малости Ьх, его можно лииеаризовальь, т.е. использовать разложение У по Ьх с точностью только до членов первого порядка: ~(х" + Ьх) =/(хе) +/„(х") Ьх+ О(ЦЬЛЦ~). Пренебрегая членами О(ЦЬхЦВ), получаем линеаризованное уравнение для Ьх: У(хе) + У„(х") Ьх = О, (3) которое уже решаешься, н можно выписать его явное решение: Ьх = — У„'(х«) У(хе), Итак, алгоритм метода Ньютона (МН) имеет следующую форму: 1) имеется некоторое уже найденное приближение х; 2) вычисляются вектор Г(х) и матрица /„(х); 3) решается система (линейных) уравнений (3); 4) пересчитывается приближенное решение х НВ х+ Ьх.
Далее процесс повторяется циклически до получения достаточно малой величины Щх) 11. Прежде чем перейти к теоретическому исследованию, рассмотрим некоторые связанные с методом вопросы. 1. Что такое /,? Это есть производная вект'ор-функцин по векторному аргументу. Точный смысл /„ определяется первым членом Решение снстем нелинейиых уРАВнений ряда Тейлора У(х + Ьх) У(х) + У„(х) Ьх. Это — векторная форма запнся отрезков ряда Тейлора для всех л функций: дУ' дУ' ау1 Ях! х ) + а Ьх1 + а Ьхз + + а Ьх н ау„а/„ау„ у'„(х„..., х ) + — Ьх, + — Ьхз+ ... + — Ьх„. е Отсюда следует расшифровка: ау ау' дх, дх„ ау„ау„ ах, "' ах„ 2.
В теоретических оценках будем использовать явную форму Ьх= — У„1У, хотя практически обычно находят матрицу у„, формируют систему линейных алгебраических уравнений (3) н решают ее с помощью стандартной программы. Так поступают в том случае, когда размерность задачи л сравнительно невелика. В дал1 нсйшем мы встретимся с ситуациями, когда ду настолько велико, что применение стандартных методов решения линейных систем невозможно нлн по крайней мере нерационально.
Обычно в таких у-у <х) ситуациях матрица у„ имеет специальную структуру, н часто удается з- х1 построить специальные методы реше- хд ння, существенно более эффективные, чем общие. При п = 1 метод Ньютона известен как «метод касательных». Этот термин поясняет рис. 1. Линеарнзация состоит в том, что кривая у = /(х) заменяется касательной, проведенной в уже най- Рнс.
! денной точке х», а в качестве следую' щего приближения х" +' берется пересечение касательной с осью абсцисс. На рис. ! показано несколько таких итераций и, естественно, возникает предположение о том, что процесс должен быть достаточно эффективным. Это и подтверждается более точным исследованием. [ч. ь !2 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ Скоднмость метода Ньютона.
Докажем теорему о квадратичной сходимости метода. Теорема 1. Пусть х' — решение системы (1). Предположим, что в некоторой окрестности х". а) Г (х) является гладкой функцией в том смысле, что существуют ее производные до второго порядка и имеет место оценка ЦУ„„(х)Ц а С; б) отображение х- г(х) равномерно невырождено в том смысле, что г„'(х) существует и ограничена: Цг'„'(х) Ц к Сг Тогда, если начальное приближение хО достаточно близко к х', метод Ньютона сходится и имеет квадратичную скорость сходимости. Точный аналитический смысл выражений «квадратнчная скорость скодимости», «х« достаточно близко к х'», «Цг',„Ц ц СВ» выяснится в процессе доказательства. Доказательство.
Будем следить за эволюцией в процессе итераций величины Цг(хь)Ц (нормы невязкн). Установим связь между Щх"+')Ц и Щх )Ц: г(х"+') = г(х«) + г„(х") Ьх+ О(ЦЬЛЦз). Используя выражение Ьх = -1„'(хь) г(х") и оценку ЦО(ЦЬхЦз) Ц ж < Сз Ц ЬхЦз (именно в этом смысле поннмаетсв пРсдположение а) теоремы), получаем У(хь+') = О(ЦЬхЦВ) = О(Цу„г Дз), откуда ЦУ( "') Ц ц С, Цу-' д!' < С,С', Цу(х') Ц', Обозначая г„= Щх«)Ц, имеем основное соотношение: ,мСгз, где С=С,С',. Эта оценка порождает следующую цепочку: г, ц Сг~«, гтрк Сг1 ж Сзг~з, гз» Сгз~ж С г«.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
