Содержание к диссертации
Введение
ГЛАВА I. Итерационные методы третьего порядка со второй производной 16
1.1. Построение класса алгоритмов третьего порядка со второй производной 16
1.2 . Исследование условий сходимости класса алгоритмов со второй производной 22
1.3. Априорные оценки погрешности 36
1.4. Исследование устойчивости класса алгоритмов (I.I.4) 54
ГЛАВА 2. Некоторые модификации итерационных методов третьего порядка 64
2.1. Простейшие модификации 65
2.2. Модификации с дополнительным значением первой производной 71
2.3. Модификации с дополнительным вычислением значения оператора 78
2.4. О решении одного нелинейного уравнения частного вида 82
ГЛАВА 3. Применение алгоритмов со второй производной и их модификаций к решению систем нелинейных алгебраических и трансцендентных уравнений 87
3.1. Вывод расчётных формул 87
3.2. О численном решении обратной задачи теории потенциала простого слоя 89
3.3. О численной реализации разностных схем для квазилинейного уравнения теплопроводности 93
Литература
- . Исследование условий сходимости класса алгоритмов со второй производной
- Исследование устойчивости класса алгоритмов (I.I.4)
- Модификации с дополнительным значением первой производной
- О численном решении обратной задачи теории потенциала простого слоя
Введение к работе
Исследование сложных научно-технических проблем нередко приводит к решению различных нелинейных задач, например, к решению систем нелинейных алгебраических и трансцендентных уравнений, нелинейных интегральных, дифференциальных, интегро-дифференциальных уравнений и их систем. Известно, что подобные задачи можно трактовать как частный случай общих нелинейных функциональных задач в конкретных функциональных пространствах, что позволяет использовать аппарат и методы функционального анализа для изучения условий разрешимости широких классов таких задач, для создания и исследования общих методов их решения.
В настоящее время известно значительное число итерационных методов и работ, посвященных их исследованию. Тем не менее, весьма актуальной является задача дальнейшего изучения и систематизации уже известных алгоритмов, а также конструирования и исследования новых методов. Это связано, в частности, с широким распространением вычислительного эксперимента как метода организации теоретического исследования сложных прикладных проблем [79І , 80 , 82 . Как подчёркивается в книге [82 А. А. Самарско - З -го и Ю. П. Попова, итерационный многовариантный характер вычислительного эксперимента "вынуждает предъявлять достаточно жёсткие требования к эффективности и экономичности численных алгоритмов, к возможности их реализации за минимальное машинное время при сохранении достаточной точности". С другой стороны, многочисленные примеры, в частности [21J, [27 J, показывают, что предварительное теоретическое исследование, проведение соответствующей экспериментальной работы приводят к повышению эффективности процесса решения прикладных задач за счёт выбора наиболее быстродействующего из алгоритмов, пригодных для их решения.
Теоретическое исследование итерационных процессов необходимо включает в себя, как известно [38J , следующие этапы:
1. установление осуществимости и сходимости алгоритма;
2. исследование быстроты сходимости;
3. эффективная оценка погрешности.
Несмотря на самостоятельное значение результатов, полученных на этих этапах, ценность каждого нового алгоритма определяется теми преимуществами, которые он предоставляет при сравнительном анализе его свойств и свойств других подобных алгоритмов. Другими словами, предлагаемый алгоритм должен показать свою конкурентоспособность с уже известными методами в том или ином смысле. Необходимыми составными элементами сравнения алгоритмов являются опробования их на модельных примерах и прикладных задачах. Сопоставление результатов теоретических исследований и экспериментальной работы служит основой рекомендации того или иного итерационного метода для решения данного конкретного класса прикладных задач.
Теоретическое исследование алгоритма (0.2) и опыт его практического использования стимулировали конструирование новых алгоритмов. Одни из них ориентированы на такие задачи, решение которых методом Ньютона-Канторовича потребовало бы чрезмерных затрат времени или памяти электронной вычислительной машины, например . Другие позволили решать уравнения, для которых не удаётся найти начальное приближение, достаточно хорошее для обеспечения сходимости итерационного процесса (0.2), например 5 J, _I IJ , 27
Уже одно перечисление алгоритмов третьего порядка и работ, посвященных их исследованию, показывает, что на протяжении мно - 8 гих лет алгоритмы этого типа вызывали и вызывают к себе значительный интерес математиков. Некоторым шагом вперёд в изучении алгоритмов третьего порядка сходимости было появление параметрических семейств (0.6), (0.10), C0.II), (0.12), (0.13), что давало определённую возможность рассматривать их с единой точки зрения. Однако следует признать, что проведённые в известной литературе исследования даже уже известных отдельных алгоритмов (0.3), (0.4), (0.5), (0.7), (0.8), (0.9) и (0.14) не были достаточно полными и завершёнными. В частности, они не дают возможности проводить сравнительный анализ алгоритмов. Дело в том, что из указанных результатов можно лишь извлечь информацию об условиях сходимости и некоторых характеристиках сходимости алгоритма, соответствующего конкретным значениям параметров. Сравнить же различные алгоритмы, используя эту информацию затруднительно или просто невозможно ввиду определённой грубости теорем и неравнозначности их конкретизации для отдельных алгоритмов.
Требует дальнейшего глубокого исследования вопрос о целесообразности использования в вычислительной практике для отыскания решения уравнения (0.1) алгоритмов третьего порядка со второй производной в расчётных формулах. В этой связи отметим работы [108 , 106 , доказывающие оптимальность метода Чебыше-ва в сравнении с методом Ньютона-Канторовича и некоторыми другими алгоритмами для нелинейных алгебраических уравнений достаточно высокой степени и некоторых нелинейных интегральных уравнений. До сих пор однако наиболее дискуссионным является вопрос о целесообразности применения подобных методов к практически важному классу нелинейных задач - системам нелинейных алгебраических и трансцендентных уравнений. Типичной в этом . Дж. Ортега и В. плане является позиция, изложенная в
Рейнболдт указывают, что.вычисление производной отображения ift в себя требует, вообще говоря, Ъ вычислений функции; вследствии этого методы, связанные с использованием производных порядка выше первого, мало привлекательны с вычислительной точки зрения, за исключением, возможно, специальных задач". Действительно, в общем случае можно предсказать теоретически, что применение итерационных методов третьего порядка для получения решения с заданной точностью может уменьшить количество итераций приблизительно в полтора раза по сравнению с методом Ньютона-Канторовича. В связи с этим, представляется перспективным использовать алгоритмы со второй производной в основном для таких уравнений, у которых процесс вычислений у(х], $ [X], 9 (х) содержит многие общие элементы и позволяет находить эти величины совместно, что значительно сокращает объём вычислительных затрат на каждом итерационном шаге по сравнению с общим случаем. С другой стороны, в связи с отсутствием результатов по исследованию устойчивости относительно погрешностей при вычислении второй производной при рассмотрении данного вопроса ранее недооценивалась перспективность простейших модификаций итерационных процессов третьего порядка со вторыми производными, а именно, возможность замены оператора $(#) каким-либо просто вычислимым оператором, хотя бы грубо приближённо аппроксимирующим вторую производную. Напомним J96J, что возможность использования вместо значений первой производной каких-либо сравнительно грубых её аппроксимаций является резервом повышения эффективности итерационных методов с первой производной. Интуитивно ясно, что подобная ситуация будет иметь место и для итерационных алгоритмов со второй производной. Тщательное рассмотрение этой стороны вопроса будет способствовать прояснению практической полезности алгоритмов подобного типа.
Целью настоящей работы является:
I. конструирование общих схем итерационных методов третьего порядка сходимости, включающих в себя как уже известные в литературе, так и новые алгоритмы;
2. исследование полученных семейств алгоритмов на основе принципа мажорант с единой точки зрения, что делает необходимым решение следующих вопросов:
а) развитие метода мажорантных уравнений третьей степени;
б) изучение сходимости семейств алгоритмов в условиях, неулучшаемых для уравнения третьей степени;
в) получение мажорантных и априорных оценок погрешности
в единых условиях сходимости;
г) исследование устойчивости алгоритмов по отношению к вычислительной погрешности;
3. анализ полученных на предыдущем этапе результатов с целью:
а) выделения конкурентоспособных по быстродействию алгоритмов ;
б) выяснения возможности использования вместо значения второй производной значения более просто вычислимого оператора с тем, чтобы уменьшить объём вычислительных затрат на каждый итерационный шаг при сохранении достаточно высокой скорости сходимости;
4. исследование различных модификаций итерационных алгоритмов третьего порядка сходимости, полученных при замене оператора второй производной каким-либо аппроксимирующим оператором;
5. проведение экспериментальной работы: опробование конкурентоспособных алгоритмов на модельных примерах и прикладных задачах с целью выбора из них наиболее эффективного алгоритма для задач данного типа.
Работа состоит из трёх глав. В главе I построен общий класс итерационных алгоритмов на основе следующего двухступенчатого подхода. Оператор 9 в уравнении (0.1) аппроксимируется суммой первых трёх (а не двух, как в методе Ньютона-Канторовича) членов разложения по обобщённой формуле Тейлора [IIIJ, а затем полученное аппроксимирующее операторное уравнение второй степени решается итерационным путём. Полученная вычислительная схема включает в себя, в частности, такие известные методы, как метод Ньютона-Канторовича, метод Чебышева, алгоритмы (0.3), (0.5), параметрическое семейство (0.6), а также множество новых итерационных методов для решения уравнения (0.1). Даётся единая геометрическая интерпретация всех рассматриваемых алгоритмов. Полезность введения новых итерационных методов, вытекающих из предложенной общей схемы, с точки зрения расширения области сходимости алгоритма и повышения его быстродействия наглядно иллюстрируется на одном вещественном уравнении.
В §2 главы I развивается метод мажорантных уравнений третьей степени. Выясняются необходимые для дальнейшего условия существования и сам вид корней мажорантного уравнения. Изучаются свойства числовых мажорирующих последовательностей. Доказана теорема о сходимости предлагаемого общего класса методов, которая одновременно решает вопрос о существовании решения уравнения (0.1), его области расположения и области единственности. Проведено сравнение полученных результатов с аналогичными ре - 12 -зультатами, известными в литературе.
В §3 главы I получены априорные оценки погрешности предлагаемого класса алгоритмов, позволяющие установить порядок и другие характеристики сходимости итерационных последовательностей. Проводится анализ выведенных оценок погрешности, что позволяет выделить из рассматриваемого класса алгоритмов конкурентоспособные по быстродействию итерационные методы.
В §4 главы I доказана теорема об устойчивости предлагаемых алгоритмов по отношению к вычислительной погрешности, которая указывает на различную степень влияния погрешностей при вычислении оператора и его производных на результат вычислений.
В главе 2 предлагается и исследуется ряд модификаций ранее рассмотренных алгоритмов. Модифицированные алгоритмы получены путём замены второй производной г каким-либо аппроксимирующим оператором оо .
В §1 главы 2 рассматривается класс простейших модифицированных итерационных процессов, в которых участвуют просто вычислимые операторы . Доказывается теорема о сходимости таких алгоритмов, указывающая на второй порядок сходимости и позволяющая утверждать их конкурентоспособность в сравнении с известными методами как второго, так и третьего порядка сходимости.
В §2 главы 2 рассматривается новое общее семейство алгоритмов третьего порядка, расчётные формулы которых используют вместо выражения со второй производной выражение с дополнительным значением первой производной. Доказана теорема сходимости данного семейства итерационных методов, получены априорные оценки погрешности. Отметим, что для известных параметрических семейств (0.10), C0.II) и (0.12) данная теорема впервые устанавливает сходимость в неулучшаемых для мажорантного уравнения третьей степени условиях и впервые указывает в этих условиях априорные оценки погрешности. Анализ результатов исследования позволяет выделить из рассмотренного семейства алгоритмов отдельные конкурентоспособные по быстродействию итерационные методы.
В §3 главы 2 аналогичным способом исследуется класс алгоритмов (0.13). Доказано, что алгоритм (0.14), обладающий наиболее простой в данном классе вычислительной схемой, имеет наибольшую скорость сходимости, что делает его наиболее эффективным среди методов семейства (0.13).
В §4 главы 2 изучается нелинейное операторное уравнение специального вида. Для решения этого уравнения предлагается итерационный процесс, использующий в качестве оператора об , аппроксимирующего вторую производную о , некоторый просто вычислимый оператор, выбор которого обусловлен видом решаемого уравнения.
В §4 главы 2 предложена модификация итерационных методов со второй производной для случая таких нелинейных уравнений, в которых совместное вычисление значений оператора j и его производных и хґ не даёт значительного выигрыша в объёме вычислительных затрат на каждом итерационном шаге. За счёт вычисления значения второй производной в специально выбираемой точке, отличной от той, в которой вычисляются оператор и его первая производная, повышается скорость сходимости итерационной последовательности. Указано, что в случае полиномиальных уравнений, порядок сходимости становится равным четырём.
В главе 3 алгоритмы, изученные в первых двух главах, при - іц меняются к решению систем нелинейных алгебраических и трансцендентных уравнений.
В §1 главы 3 выведены расчётные формулы итерационных процессов применительно к рассмотренному типу уравнений. Сформулированы некоторые практически полезные рекомендации по использованию для решения систем нелинейных алгебраических и трансцендентных уравнений методов со второй производной.
В §2 главы 3 рассматривается вопрос о численном решении обратной задачи теории потенциала простого слоя. Проведение сравнения различных конкурентоспособных алгоритмов, пригодных для решения системы нелинейных уравнений, возникающих в данной задаче, позволил выбрать наиболее эффективный по быстродействию алгоритм.
В §3 главы 3 рассматривается вопрос о численной реализации разностных схем для квазилинейного уравнения теплопроводности. Как показано на серии примеров, алгоритм из §4 главы 2 позволяет получить решение с заданной точностью за меньшее машинное время, чем алгоритм, применявшийся к решению этой задачи ранее.
Все расчёты,. результаты которых используются в данной работе проводились на ЭВМ ЕС - 1020.
Для теорем, замечаний и формул в работе принята трёхступенчатая нумерация. Первое число означает номер главы, второе-номер параграфа, третье - номер теоремы (замечания, формулы). Нумерация рисунков и таблиц состоит из одного числа - порядкового номера в данной работе.
Основные результаты, изложенные в работе, опубликованы и докладывались на семинаре по вычисли тельной математике в Ленинградском университете им. А. А. Жда - 15 -нова (1983 г., руководитель - профессор И. П. Мысовских), на семинаре по вычислительной математике в Иркутском пединституте (1980-1982 гг., руководитель - профессор Б. А. Бельтюков), на итоговых научно-методических институтских и зональных конференциях (1980-1982 гг.), на II республиканском симпозиуме по методам решения нелинейных уравнений и задач оптимизации (Хаапса-лу, 4-7 июня 1981 г.).
Пользуясь случаем, автор благодарит своего научного руководителя профессора Б. А. Бельтюкова за постоянное внимание и всестороннюю поддержку при выполнении настоящей работы.
. Исследование условий сходимости класса алгоритмов со второй производной
Здесь запись, например, 4(3) означает, что сделано 4 шага по методу Ньютона для основного уравнения и 3 шага по методу Ньютона для более простого аппроксимирующего уравнения. Использовались следующие значения констант:8 =0.0001, 0 =0.1, 6 =0.01. Как можно видеть из приведённых результатов, выбор по правилу (I.I.5) позволяет существенно ослабить ограничения на выбор начального приближения и уменьшить объём вычислительных затрат, необходимых для получения решения с заданной точностью.
В случае алгебраического или трансцендентного уравнения (I.I.I) алгоритмы из (I.I.4) допускают единую геометрическую интерпретацию (рис. 1-3). Если известно некоторое приближение Х к решению X уравнения (I.I.I), то для получения приближения З через точку [Х ,Щ(п)) проводится парабола U - 9 (сс), имеющая с кривой - ЩХ) касание второго порядка. Если ОС =2, то значения элементов вспомогательной итерационной последова тельности j Xf k равны абсциссам точек пересечения касательных к параболе Ц = (х) и оси Ох . При 0І =1 для определения значений и используются хорды параболы, проходящие через точки (% 9пРл/Iй фиксированную точку ( ( xj) . При (л/=0 используются прямые, параллельные касательной к параболе в её фиксированной точке (# , ( ))- Количество уточнений по параболе определяется числом S . о Рисунок I К t Vі ХЛ х оС = 0 Рисунок 2 Рисунок 3 l& 1Х,1 я= 1 а: - 22 1.2. Исследование условий сходимости класса алгоритмов со второй производной Для исследования вопросов сходимости процесса (I.I.4), включая простейшие случаи =4 и 4 , применим принцип ма жорант , используя в качестве мажорантного уравнения алге браическое уравнение третьей степени где П0, ч » о положительные числа. Обозначим Лемма І.2.1. Если П0 1 , то уравнение (І.2.І) имеет три действительных корня І І Г0ал(2 Щ- А ; 2-2 причём где Доказательство . Преобразовав уравнение (1.2Л) обычным путём к неполному виду, покажем, что - 23 где 9 ъ о Имеем О! / Q= - ((іН. о+0.?5о4Но(і- ))-(і+ Тогда неполное уравнение, а вместе с ним и уравнение (I.2.I) имеют по три вещественных корня, причём для (1.2.I) эти корни суть (1.2.2). Остаётся выяснить взаимное расположение корней. В силу того, что можем записать Зи2- шмя-$о) откуда следовательно, Убедимся в справедливости неравенства (1.2.3). Оно вытекает из элементарных соображений, если учесть, что функция т(т) имеет положительный максимум в точке $ =-fir(-i-/i+ ) » неположительный минимум в точке и тот факт, что щО)=ю Q .
Доказательство. Свойства 4 и 3 очевидны, так как Чу,"("Ь)=Мо 0 и СК і )=Ио-і+Ко 0 при -Ь 0 . Второе свойство следует из того, что производная У (ір М-І+ІСі-І возрастает на 10,- "[» при этом 4 (0)=-1 /і у$їГЛ=(? Наконец, свойство I получаем, исходя из того, что Ц (о)— ОУ0 , а \, есть первый по величине положительный корень. Лемма доказана.
Образуем теперь итерационную последовательность (1.1.4) для алгебраического уравнения (1.2.I). t 0,l,2,..., -l (К=К), где Введём обозначения Заметим, что при Н0 1 и {[0 і [все эти величины положительны в силу леммы 1.2.2. Данное замечание будет использовано в следующей лемме. Лемма 1.2.3. I. Если Н0 1 и \[0 1 \ , то Y\tb i и g a l , где - 25 -2. Если Н0=1 и- [0,4 [ , то Н =1 и g = 1 . Доказательство . Прежде всего докажем спра ведливость соотношения Н„- (і -НкХ С у1) (1.2.7) Разлагая производную V (і) по степеням /с-"" ,)» где номер Ь произволен, будем иметь v (-0= КУ ММ+ Y" ( X-M Тогда положительный корень уравнения Г(і) 0 нетрудно представить в виде Исходя из этого, находим при этом очевидным является равенство из которого и следует (1.2.7). В свою очередь из соотношения (1.2.7) получаем оба утверждения леммы относительно п , полагая к-О. Далее, вставляя выражение для п через Н в (1.2.6), можем записать _ -0.5 + 1.5fi+j , ,, I -0.5 + i.5(l+S,C] Поскольку -a5+i.ff n,)- +ftfS=Q5( -l)( +i) - (i+п,У( гг- І)=(к- i)(- и„ о. РГ- л 5]= - 26 =( - L)(- K (RT- -5)-Q ff) i TO В силу чего из (1.2.8) следует оба утверждения леммы относительно у . Лемма доказана. Лемма 1.2.4. Если Н 4 1 , „ I JM то вспомо-гательная последовательность JU (, =0,1,2,..., определённая (1.2.5), обладает свойствами I. 2. к , -Jf 3. ; где -1 меньший положительный корень уравнения 4,(-1)=0, (I.2.I0) а -і - меньший положительный корень уравнения (I.2.I). Доказательство . Соотношение помогает установить существование корня (1.2.9), причём очевидным является неравенство таким образом свойство 2 выполнено при К=0 . Заметим далее, что справедливость свойства 3 последует из свойства 2, если мы покажем, что і . СІ.2.І2) - 27 -Поскольку №) = №) - г (є) = wj+У № - ) + а то, следовательно, существует корень уравнения (1.2.10), принадлежащий интервалу ji -і Г, а поскольку - наименьший положительный корень этого уравнения, то (1.2.12) становится очевидным . По определению то есть, и свойство I выполнено при к = О . Предположим теперь, что свойства I и 2 справедливы при всех / =0,1,2,..., , и покажем их справедливость и при lc+1,
Исследование устойчивости класса алгоритмов (I.I.4)
Замечание I.2.I. Приведённая теорема, прежде всего, представляет собой теорему о существовании, единственности и Л/. области расположения точного решения X уравнения (I.I.I). Отметим, что теорема 1.2.I при определённом соотношении между постоянными г , р0 , К0 , Ио . К(к )Г0/(х),о) может конкурировать с соответствующей теоремой JI. В. Канторовича из [38], основанной на применении мажорантного уравнения второй степени, позволяя в ряде случаев сделать заключение о существо-вании, единственности и области расположения решения X уравнения (I.I.I) там, где условия теоремы J1. В. Канторовича не выполнены. Например, если JKo . 4 (l+l Zo) к ь(і+7„р что возможно в том случае, когда оценка второй производной в точке Х0 значительно меньше, чем её оценка в области QQ , то основные константы двух сравниваемых теорем связаны неравен ством / N
Следовательно, при определённом соотношении между оценочными константами будут выполнены следующие неравенства: Н.4 1 (что и требуется в теореме I.2.I) и к 0.5 (что означает нарушение условий теоремы б 1 главы X VJU из [38].
Далее, поскольку условия существования решения X являются одновременно и условиями сходимости метода Ньютона-Канторовича, -то приведённые рассуждения показывают также возможность уточнения области сходимости этого метода при использовании для её определения теоремы I.2.I. Проиллюстрируем сказанное на примере уравнения
Выберем в качестве начального приближения Х = ЪЛО и положим 1=0.40 . Вычисление соответствующих констант показывает, что условия теоремы I.2.I выполнены ( \\0 =0.80, і =0.39,1. =0.94), а условия теоремы из [38J нарушены, поскольку меньший положительный корень мажорантного уравнения второй степени оказался больше, чем значение Ї . При проверке условий теорем для того же самого X =3.10 и большего значения 1 =0.80 оказалось, что о условия теоремы I.2.I снова выполняются ( И0 =0.83, -L =0.39, =0.89), а теорема из [38] опять не может быть использована, поскольку ті =0.59, то есть мажорантное уравнение второй степени не имеет действительных корней.
Отметим, что при проверке условий теоремы 1.2.I можно не вычислять значения корней мажорантного уравнения третьей степени, которые имеют довольно сложные аналитические выражения. Достаточно знать лишь знаки У (i) , V (і) иН0-і . Если, например, У(г) 0 , то теорема 1.2.1 гарантирует существование, единственность решения X уравнения (I.I.I) в области ъ 0 , а также сходимость к этому решению любого алгоритма из класса алгоритмов (I.I.4).
Оценки погрешности (1.2.13), полученные в предыдущем параграфе, обладая тем несомненным, .достоинством, что они являют - 37 -ся неулучшаемыми для мажорантного уравнения (І.2.І), мало пригодны однако для априорного анализа свойств итерационных методов из класса (І.І.4). Для выяснения различных характеристик сходимости рассматриваемых алгоритмов, в частности, порядка сходимости, на основе (1.2.ІЗ) в данном параграфе будут получены априорные оценки погрешности, что даст возможность выяснить конкурентоспособность отдельных алгоритмов из (1.1.4).
Модификации с дополнительным значением первой производной
В большом количестве работ, в частности, в ҐІ-4], [42_, [48] , [50j , [73-7 , II4J , рассматриваются итерационные методы третьего порядка, не требующие вычисления второй производной, а использующие взамен дополнительное значение первой производной на каждом итерационном шаге. Упомянутые алгоритмы близки по своей природе, поскольку основаны на той или иной аппроксимации суммы первых трёх членов разложения исходного оператора по формуле Тейлора. Однако авторами выше перечисленных работ данные методы рассматриваются разобщённо. В результате полученные условия сходимости и характеристики скорости сходимости практически не сравнимы, а роль числовых параметров не достаточно ясна. В данном параграфе построен один общий двупараметрический класс итерационных методов третьего порядка, установлены достаточные условия сходимости, точные для мажорантного уравнения третьей степени, получены априорные оценки погрешности, анализ которых позволил выделить из рассмотренного класса конкурентоспособные по быстродействию алгоритмы.
Исходным материалом при построении нового семейства итерационных процессов послужит класс алгоритмов (I.I.4) при L = 6. Используя разностную аппроксимацию (Ъф О) приходим к следующей модификации алгоритма (1.1.4) - 72 (2.2.1) Как видим, полученная итерационная схема не содержит значений второй производной, но требует взамен на каждом итерационном шаге одного дополнительного значения первой производной tr
Теоре.ма 2.2.1. Пусть выполнены все условия теоремы 1.2.1, и кроме того, пусть $ 0,45 , тогда на алгоритмы (2.2.1) переносятся все утверждения теоремы I.2.I и теоремы 1.3.1 с той лишь разницей, что последовательность] Цго О] строится в соответствии с (2откуда видно, что с уменьшением значений параметра Ijb , а также с увеличением значений другого числового параметра сходимость итерационного процесса убыстряется. Такой же вывод может быть сделан и на основе априорных оценок погрешности. Итак, наиболее быстро сходящейся итерационной последовательностью из рассмотренного класса (2.2.1) является последовательность с X-Z и -0J6 t отвечающая алгоритму Джарратта j 95J, ИЗ] . В этом частном случае можно уточнить оценки по грешности, поскольку где 4 (И) = Н 4 . Ш(і-Щ і при И Є (_0, Ц , что доказывает четвёртый порядок сходимости данного метода в условиях теоремы 2.2.1. Однако некоторые другие алгоритмы могут конкурировать с этим методом вследствие некоторого упрощения расчётных формул (2.2.1) при 01=0,(1= 1 и при р =1 . Окончательно из рассмотренного множества значений числовых параметров cL и fb выделяем лишь следующие пары: .2.1), В данном параграфе исследуется класс алгоритмов третьего порядка без второй производной, но с дополнительным вычислением на каждом итерационном шаге одного значения самого оператора iP . Ранее это параметрическое семейство методов и его отдельные члены рассматривались в ряде работ, например, в Г70І, J62J, 185 , 1101 . В настоящем параграфе впервые проведено исследование сходимости таких методов на основе принципа мажорант, как и в предыдущих параграфах применяется мажорантное уравнение (I.2.I), изучается роль числового параметра, выбирается его оптимальное значение.
Итак, полагая в (I.I.4) $ = 2 и L-0 , а также используя разностную аппроксимацию (ХФ О) приходим к классу алгоритмов
Теорема 2.3.1. Пусть выполнены все условия теоремы І.2.І, и кроме того, пусть у 0.5 , тогда на алгоритм (2.3.1) переносятся все утверждения теоремы 1.2.I и теоремы 1.3.1 с той лишь разницей, что последовательность ігі)\і0- О) строится в соответствии с (2.3.1), а вид Доказательсто теоремы завершается стандартным способом. Теорема доказана.
Замечание 2.3.1. Анализ формул (2.2.3), равно как и априорных оценок погрешности, показывает, что уменьшение значения параметра У влечёт возрастание значения очередного члена последовательности it Л » то есть, убыстряет сходимость итерационного процесса. Выбирая значение у наименьшим из возможных, приходим к алгоритму (К О-5
Сравнение расчётных формул (2.3.1) при различных значениях параметра )( показывает, что выделенный алгоритм (2.3.5) требует и наименьших вычислительных затрат при отыскании каждого следующего элемента итерационной последовательности \ X \ Таким образом, сравнительный анализ оценок погрешности и вычислительных затрат позволяет утверждать, что в классе алгоритмов (2.3.1) алгоритм (2.3.5) оптимален. Данный алгоритм представляет собой фактически чередование основного и модифицированного методов Ньютона-Канторовича при решении основного уравнения (I.I.I). Теорема 2.3.1 впервые устанавливает сходимость этого алгоритма в неулучшаемых для мажорантного уравнения третьей степени условиях, показывая в этих условиях третий порядок сходимости.
О численном решении обратной задачи теории потенциала простого слоя
Под обратной задачей теории потенциала понимают Гб7 задачу о нахождении формы области по заданному внешнему потенциалу и при заданной плотности. В работе Гб7 поставлена задача для потенциала простого слоя.
Пусть существует некоторая замкнутая плоская кривая , создающая потенциал 1L ( м) = - М &v Ч, ( А ) d А где /Л-(А) - плотность фиктивных зарядов на кривой в переменной точке А , М - произвольная точка вне кривой у ,1(А,М)-расстояние между точками А и Ґ\ , cLe - элемент дуги кри-вой X . Пусть С - некоторая фиксированная окружность, содержащая внутри кривую X На этой окружности задаётся значение потенциала U(M) , то есть, u(M)-(M)?MC
Согласно 67 определение кривой по заданной плотности о как функции полярного угла и известной функции t(M) сводится к решению интегро-дифференциального уравнения первого рода 2 —7 Ф)-[ )Ьь[і/{Є ty (3.2.1) где О О іУь і "Cl fJ O f Z i _ полярное уравнение искомой кривой, Л - радиус окружности С . Пусть + 1 о Ц с ЗС ; и искомая функция обладает свойством симметрии В работе J67J предлагается свести (3.2.1) к бесконечной системе, представив функции Ъ[ f) и 4(@) соответствующими рядами Фурье. К полученной системе уравнений где JT 4- к+і - коэффициенты Фурье функции (&) , предлагается применить метод "редукции", а именно, выбирается достаточно большое Д/ и рассматривается система N уравнений с N неизвестными
В работах I67-69J начальное приближение для итерационного процесса выбирается случайным образом, и этим мотивируется необходимость использования для полученной системы уравнений различных вариантов метода спуска.
В данной работе мы предлагаем использовать в качестве начального приближения окружность, то есть, один из векторов вида ( f О, О, ... з О) , выбирая значение первой координаты этого вектора из следующего естественного условия l (C,0,O,...,0)l=o jKf1;0,0,...,o) СЗ.2.3) Функции (х) имеют в точке (Чі,0?0?..( Оу довольно простой вид ,0,9,...,0)=(4) «п- "тН" поэтому удовлетворительное приближение для можно найти за незначительное машинное время. Предлагаемое начальное приближение обладает ещё и теми достоинствами, что, как нетрудно показать, существует непрерывный линейный обратный оператор 0 = 1 (сСо)} , а оператор (00) является ограниченным по норме. Третья производная з ( ЭС-/ ограничена в любой замкнутой области, не содержащей точку (0,0,...,0). В случае достаточной малости по норме невязки v(%i)0,0}..,fO) будут выполнены достаточные условия сходимости из теоремы 3.I.I.
На серии примеров (исходные данные взяты нами из работ - 92 -67-69 проведено сравнение различных методов решения системы уравнений (3.2.2), исходя из начального приближения ($Lfl,Or..; 0), Оказалось, что наиболее эффективным является алгоритм (I.I.4) при (L-Z и выбором $гъ п0 правилу (I.I.5)
Таблица Исходные данные МетодIвариантI Метод2вариантI Метод2вариант2 Метод3вариантI Метод4вариантI Метод4вариант2 Л/=3 =3.5 Го=2.4190 i =0.4572 , =0.1977 II ит.816сек. 6 ит.832 сек. 6 ит.608 сек. 5 ит.424 сек. 6 ит.ШОсек. 6 ит.864 сек. л/=зR =5.0 Го =3.1350 .=-0.1180 V0.0I0I 8 ит.613сек. 9 ит.1014 сек. 9 ит.750 сек. 7 ит.557 сек. 6 ит.980 сек. 6 ит.869 сек. д/=3 R =2.5 їо =3.7230 tL =-0.2210 =0.0277 8 ит..613 сек. 7 ит.767 сек. 7 ит.630 сек. 4 ит.356 сек. 5 ит.826 сек. 4 ит.601 сек. У =4 R =2.5 г. =3.723 її=-0.2210 =0.0277 Г =-0.00438 неосуществим 9 ит.1578 сек. 9 ит.1200 сек. 5 ит.634сек. 6 ит.1706 сек. неосуществим
Применялись следующие методы: 1. метод Ньютона-Канторовича; 2. два варианта метода спуска, применение которого рекомендуется вГб7-68] (варианты отличаются тем, что при проверке спуска в первом варианте вычисляется только значение о (#у , а - 93 -во втором с целью снижения общих вычислительных затрат одновременно вычисляется и Р(Х). 3. алгоритм (І.І.4) при cL Z с выбором аиз (I.I.5); 4. метод (0.10) со "спуском" - первый вариант и без "спуска" - второй вариант (U = О Л 5 ) t Результаты расчётов приведены в табл. 4, здесь указаны затраты машинного времени и соответствующее количество итераций. Сопоставление результатов показывает, что наилучшие результаты даёт применение алгоритма 3.
Дополнительно было проведено сравнение алгоритма 3 с другими алгоритмами из (1.1.4), в частности, с методами (0.3), (0.4), (0.5). Установлено, что за счёт специального выбора (по (I.I.5)) значений 0 повышается быстродействие алгоритма (I.I.4) и расширяется его область сходимости, что хорошо согласуется со сделанными ранее теоретическими выводами.
О численной реализации разностных схем для квазилинейного уравнения теплопроводности В работе 83Ідля численного решения уравнения теплопроводности со степенными коэффициентами г Г= Х "&(, о) = АМ ) ; предлагается использовать разностную схему "с опережением" Ф(х)=А(х)х+х-0, (3.3.1) где Л[сс) - трёхдиагональная матрица с компонентами Q- - 94 ЯҐ и fb шаги соответственно по времени и пространству; Э 9 и CP - L - вещественные параметры, f.-l -ая координата вектора Х= ГіЛг,.---; л/) Для получения решения X системы уравнений (3.3.1) обычно j_83J используют алгоритм і/ о - #rj3W = V= ,1,2,... -3-2) На ряде модельных примеров из Г83І проводилось сравнение метода (3.3.2) и алгоритма (2.4.3), в котором выбиралось в соответствии с (I.I.5). Программы для реализации этих алгоритмов были написаны на языке Фортран и предусматривали выполг нение вычислений с двойной точностью. Расчёты проводились на ЭВМ EC-I020. Оказалось, что применение метода (2.4.3) сокращает время счёта на каждом временном слое на треть. Эффективность применения метода (2.3.4) особенно ярко проявляется при использовании грубых временных сеток.
