Исследование сходимости и устойчивости одного многоступенчатого итерационного метода и некоторых его приложений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Р Г 5 О А Ка "Р33035 РУХОЛЯСП

Кумкиоиа Ольги Влаидонрэдиз

НССЛППОВЛПН!; СХОДИМОСТИ И УСТОЙЧИВОСТИ ОДНОГО ЯЮГОСТУПЕ!IЧ АТОГО ИТЕРАЦИОННОГО МЕТОДА И НЕКОТОРЫХ 5Р0 ПРИЛОЖЕНИЙ

О 5.01 л>7 - мписятгяияя клтюпга

ЛВТОГЕФЕРЛТ

ия соискгдш« уч&гэй стспс-ш тиидатз '' ^гта^матаптн'колх наук

Иркутск • ? 995

Работ» выполнена на кафедре математического ашдоа Иркутского государсгаеиного педагогического института,

t

Научный рукоаодатевьлектор фюико-матештачваоа наук, академик МАН ВШ Бсиьтшю» БЛ.

Официальные оппоиеншаоктор технически» наук,

профессор Татюшкин АЛ.,

кандидат физико-математических наук, доцент Лпарцин A.C.

Ведущая организация: Иркутский вычислительный центр СО РАН

Защита состоится 1995г-

■ -/Р часов на заседании диссертационного совета Д 063.32.04 по защитам диссертаций на соискание учёной степени доктора физико-математических наук в Иркутской государственном университете (664003, Бульвар Гагарина 20, Ьй корпус ИГУ).

С диссертацией можно ознакомите« в Научной библиотеке Иркутском

государственного университета (Бульвар Гагарина, 24) #

Автореферат разослан "АГ n,OC*>ft'C 1995 годе.

Учёный секретарь диссертационного совета ,

к.ф.-м.н„ доцент У Н.Б. Бельткжо»

О&шодгсшяшшшцш&цы

н<хть темц. Несмотря на значительное число итерационных методов и пссвкщенных им работ, весьма актуальной остается задача дальнейшею изделия и систематизации известных алгоритмов, а также конструирование и исследование новых , обладающих теми или иными преимущества ми. Многочисленные примеры показывают, что' важную роль играет предварительное теоретическое исследование метода, так как оно может существенно повысить эффективность процесса и сократить время решения прикладной задачи. Имеется в виду выбор "хорошего" начального приближения, установление области расположения решения и области единственности, получите условий «единоеги и опенок погрешности приближенного решения. В частности, представляют интерес результаты такого исследования для некоторых важных классов уравнений, встречающихся в теории околозвуковых газовых потоков, теории теплопроводности. Вместе с тем, широкое внедрение в вычислительную практику ряда известных эффективных методов решения нелинейных задач существенно сдерживаются именно их слабоЯ теоретической изученностью. К их числу можно отнести, о частности, метод П-Р-Н (Писмзна-Рэкфорда-Ньютона), который обладает в ряде случаев преимуществом перед методом Ньютона. Например, он не требует вычисления и обращения производной оператора F(x), что может оказаться весьма выгодным, когда это требует слишком больших вычислительных затрат или существенного видоизменения традиционного метода. В то "де время метод П-Р-Н до енх пор плохо подпевался теоретическому исследованию. Для него отсугствояали условия сходимости, практическая проверка которых не требовала бы знания точного решения исходной системы уравнений. Оставались неизвестными для указанного метода и какно.шбо оценки погрешности приближенного решети, не исследовалась его устойчивость к погрешностям вычислений и некоторые другие вопросы. Отметим, что несмотря на самостоятельное значение результатов теоретического исследования каждого нового алгоритма, его ценность в значительной мере определяется теми преимуществами, которыми он обладает по сравнению с наиболее известными и часто применяемыми методами. Последнее является одним из основных показателей конкурентоспособности алгоритма. Все сказанное естественным образом стимулирует конструирование новых алгоритмов ориентированных, например, на задачи, решение которых известными методами требует чрезмерных затрат машинного времени или

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

Пусть дано уравнение

Р(х)=0, (I)

где Р- нелинейный непрерывный оператор ш множества 5 банахов« пространства X в банахово пространство У.

Введем для уравнения (I) операторы Ф,(х,у), ¡ = 1,ш, действующие из X х X в У ( X, У - банаховы пространства) и удовлетворяющие следующему основному условию:

Каждое х" б Б с X для которого Ф,(х*. х*)=0, 1 = 1,го является р ешениеи уравнения(1).

Предлагаемый класс итерационных методаз для решения уравнения (1) ¡¡мгет вид

(»)_ (п) г '/ (»( <а|ч -I , <»> (п). ; _ ГII xi -хы~1 Ф|1х|-1'х|-|М ФЛх|-|.*1_|> • 1 — ».га (/)

Здееь Хо" - начальное приближение, = Фд»,у) • частная

производная в смысле Фреше оператора Ф,(х,у) по первому аргументу (1 = 1,ш ), т - параметр, задающий число ступеней процесса на каждом итерационном шаге. Предлагаемый процесс (2) фактически является широким классом итерационных методов типа Ньютона. В общую схему этого процесса при соответствующем выборе операторов Ф,(х,У). * = 1,пг укладываются, например, методы последовательных приближений ( Ф1(х,у) = х - в (у), 1 ■= 1,ш) Ньютона - Канторовича ( Ф({х,у) =Р(х), 1 = 1,т), процесс ПВР - Ньютона, П-Р-Н ( см. § 2,3 главы 2 рабош ) . Работа посвящена исследованию сходимости процесса (2) и его устойчивости к погрешностям вычислений. Рассмотрены приложении этого процесса, как для исследования уже известных, но недостаточно, изученных итерационных методов, так и для построения новых аффективных алгоритмов решения некоторых типов нелинейных уравнений. <

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

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

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

4. Проиллюстрировать эффективность построенных алгоритмов на решении одного класса прикладных задач.

Методы исследования. При обосновании сходимости и устойчивости процесса (2) кепельзована1 обшая теория итерационных мстодоэ типа Ньютона, в частности] понятие ааясорантиой последовательности в смысле Л.В.Канторовача. Условия сходимости н устойчивости методов ПВР-

Ньютона, П-Р-Н к предложенных методов решен:« уравнений вида (I) получены из общих результатов исследования процесса (2) при соответствующе! I выборе операторов Ф|(х,у), I = 1,т .

Научная новизна. Предложен процесс (2) решения нелинейных уравнений вида (!). Формулируются и доказываются теоремы о сходимости процесса (2). использующие оценки корм обратного оператора в точке начального приближгння н в некоторой облает;!. Одновременно решается вопрос о существовании решения уравнения (I), его области расположении и области единственности. Исследуется устойчивость процесса (2) к погрешностям вычислений всех входящих в него элементов, а том числе начального приближения. Решается сопрос о возможности расширения области сходамоста процесса (2). Устаказлнзастся возможность использования метода (2) для получяпа монотонной сходимости. Формулируются и доказываются сооютстяуккцис теоремы.

Полученные общие теоретические результаты исследования схсгщчссгл н -устойчизости процесса (2), в указанных выше частных случаях ( метод Ньютона, процесс с неравноправными аргументами ), либо совпадают с изЕгстыии утпгрмцдай'лмн, либо уточняют ¡ши дополняют их, л::бо, наконец, воебшг к« имеют аналогов 8 литература.. Выводятся практически прозеряемие условна сходамоста, оценки скорости сходимости и оигюси пограиности иетодса ПВР-Ныотока, П-Р-Н, которые в литературе не известны. Разработаны к кссле&овдзы новью алгоритмы решении урэвигжи (1> а частности методы НПВР - Ньютоне и СПВР-Ньктша.

Установлены условия и* сходимости. Проведены численные эксперименты, подтверждающие эффективность предлагаемых методов.

Практическая ценность. Предложенные в работе алгоритмы могут быть использованы для численного решения на ЭВМ нелинейных уравнений вида (1). С иомошыо этих алгоритмов'получены численные решения класса квазилинейных эллиптических уравнений, возникающих в теории околозвуковых газовых потеков. Полученные теоремы могут быть использованы для установления существования точного решения соответствующего нелинейного уравнения, его области расположения, а о ряде случаев и области единственности,

Апробация работц. Основные результаты опубликованы ъ [ I], [ I), [ 3 ], [ 4 ], и докладываюсь на семинаре по вычислительной ?.штематмкз! и Иркутском государственном институте (1984-1994 г.', руководитель профессор Б.А. Белымков), на итоговых научно-методических институтских и зональных конференциях, на конференциях молодых ученых, проходившие в ИГУ в 1987,1938 годах.

Структура и обт-см работы, В соответствие с основными задачами, постипленнмми в рабо гс, диссертация состоит из введения, трех глав, заключения, списки литературы.

Текст диссертации изложен »а 113 страницах машинописного текста, включает 5 таблиц. Список литературы содержи! 101 наименований ( 69 отечественных, 39 иностранных источников).

СОДЕРЖА Н И Е РАБОТЫ

Во введении (стр. 2 ) содержится сбзор н краткая характерна!»-« работ, близких к теме диссертации, и Тйкже схематично излагвюгса ек оснопные результаты.

В главе 1 (сгр, 16 ) формулирую гсу и дохазыасются -ггоргыы с сходимости процесса (2;, использующие оценки норм обратного оператора » точке- начального приблшкеша н в некоюрей области. Одноараденг« рычаетез еопрос о. сущестсованин радения уравнения (1), сто облаекз расколожелия и области единственности { §! ). Исследуется устойчивости процесса (2) к погрешностям вычислений всех входящих в него зпеиентоа, к том числа начального приближения (3). Решается вопрос о возможности расширения облести сходимости процесса (2) (§•!). Устгназлпвастся еозиохтсть кгпользовени?. метода (2) для получении монятонс^И сходимости (§3).

б"

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

Ниже при водятся некоторые основные результаты первой главы.

Теорема!. Пусть выполнены следующие условия (1»1,т):

1)13шаре5 = { х в X: |х-х™|<;г}

существуют линейные обратные операторы Г|(х^0)) = [Ф^х^.х^1')]-1 и известна оценка

|г,(х<0,)|<В (хеБ).

2) для х^ еЭ выполняются условия

3) для любых х, у, 6 Б справедливы условия

|ф,(х,х)-ф,+1(у.х)|<г |х-у|.

4)В<У <1, ВЬЯ <4(1-В<У) ,

'о 2

5) г>И, где Г • меньший корень уравнения 1ви2-(1-в^)1+ Я,=0,

Тогда в шаре У = | ш X; Цх-х^'^Чсуществует единственное решение уравнения (I) к которому сходится процесс (2) с быстротой

,«>!о ,(П),.(п-1)_

4 '' вг^-1

В работе получены также ряд других условий, гарантирующих сходимость процесса (2), которые являются, в некоторых случаях, менее ограничительными по сравнению с приведёнными в теореме I.

. Определённый интерес представляют условия монотонной сходи ¡¿ости метода (2)..

Т е о р с и а 2. Пусть выполнены условия О е Яп выполнены следующие условия для всех 4 = I, га:

1)Х0 5Х<<>>. <Х0,Х<0)>СО Ф1(Х0.Х0)^а:£Ф1(Х<0>.Х<0>>.

2) Существует такая неотрицательная матрица Р € Ь (Яп), что

1Ф, (X ,Х )Г' *Р~£0, Хо .

3).Для х0<;х^у2х^0)

ф, (У. У)■■Ф1+|(*.х) * Ф,(У.У)(У-X)

Тогда на порядковом интервале <х0,х^0> »существует решение х* уравнения (1), такое, что

х{"> 4- х* при п -*<х> (1 = 1,и»),

причем

I 2 Ш

Итервции в рассматриваемом процессе фактически находятся по формуле

У

:_<») _<П) _(П) _(П) _(П) _(П)

XI - XИ -[ф',(Xм . X и)+ *2*в>ГЧ<Е»4< * 1-1 • * 1-1)+ ,

1 - 1,ш,

_(0) _(0) гдех£°-*о ,/;->, I™, - Xо ,»I™ сел.погрешности

_<0) _(п)_(п) _(п) _(п)

слений соответственно значений х о ,Ф( (х и , х н ),Ф|( х ы , х ы ),

_(п) _(П) _(п) _(П)

-[ф,(Xм . Xы ) + ^'»ГЧФ,(Х|-1, ХИ)+»;■"] .

Для практического использования итерационного процесса (2) еесьиа

0 выяснить при каких условиях малые (по норме) погрешности _(»> _(п)

хо , I™, I™, приводят к малых же погрешностям х? - х и ,т.е.

тся ли процесс (1) устойчивым к погрешностям вычислений начального шження х<°>, функций Ф( (х^.х}^) н их честных производных

Несомненный практический и теоретический интерес

тгвляет также получение оценки погрешности |х* - х{п*|, п=0,1....

р е ы а 3. Пусть в шаре Б = ( х 6 X: |х — | ^ г > выполнены условия

1 из теорем ! или 2 а = 1,т). Кроме того

1). Для всех х е Б существ /ют линейные обратные операторы Г,(х )-[Ф,(х ,х )Г'и |Г|(х )|г;В ,

2). Для всех х, у е Б справедливы неравенства (*.*)- (У. У)| ^ I- - у| ,

|ф1(х,х)-ФИ1(у,х)|^5 |х — у| .

I -<0)1

э^-,. «г, ¡1

i»l,ra, j» 1,3,11=0,1,...,

4).B(<y+L;3b*2*)<l, iCESO-D)1,

где

' BL _

V » —.......... .U« » »—I .41 ■ .. I.I I II» .

2(1-Bf) 1-Bff

5).T0<T**, для L i» О, V* больший корень уравнения

Ci2-(I-D)r+E«=0 , (3)

6). rit'+p, p = max (T0 ,Г),

T- меньший корень уравнения (3).

Тогда справедливы оценки

I -<п>1

j<0) В сг*а '»+ D*<■ 0 + Е S/?,

f-lim ^.i-im.

Я «о

Применение общих результатов исследования процесса (2) позволяет получить (при соответствующем выборе операторов Ф^х.у), i = l,m) новы« теоремы о сходимости и ( или ) устойчивости ряда известных итерационны} методов, таких как методы ПВР-Ньютона, П-Р-Н.

В главе 2 (стр.45) с помощью результатов главы I выводято практически проверяемые условия сходимости, оценки скорости сходимосп и оценки пшрешности методов ПВР-Ньютона, П-Р-Н, которые в литера1>рс

ГО

ивеслкл. Для этс1х> предварительно Остановлено, что эти методы можно сматривать в качестве частных случаев процесса (2) при указанном ннже 5оре операторов Ф|(х,у), ¡»1,ш. Для метода П-Р-Н: т=2,

Ф,(х,у)о Qtx,y) + FH(x)+Fv(y) ,

ф,(х.y)«a(x,y) + FH(y)+Fv(x) ,

«>0, F(x)-F„(x)+Fv(x).

Для метода ПВР-Ньютона

Ф|(Х.у)«={8,-»(.......................................sm-tm)T,

ra I

4'l(8|.y) = 2B|jtj++g1(t,)-cl+-~{ei|(s,-t,) + gi(8¡)-g¡(t,)] .

J=! W

У =• <t(). i»l,ra . Метод ПВР-Иьютона исслздозаи тякже для систем айда

2>ljtj+giO|)-Ci, «— 1.1с . (4)

И

где g,(l) неяинейше функции ( § J) .Такие уравнения возникают, pirwcp, при разностной еппрошшаши каазилкмейных эллиптических

JHtílüiV

Получен«« сбгцие результат нслользЬвчмы для получения оценки хшисстк метода ИВР-Нштона & нрнменешш к классу уравнений

r ¿u ^ ,с 2 и , д 7ич .

ь ' дх д у

oajir, йз'кпос з.чзченкз в теории околезвукошд газовых потегез и жулярных взанмолгйстанЯ. С помощыа тгестнмх. в литератур« петита эти оценки sí® могли быть получены.

П

Глава 3 посвящена применению метода (2) для полупани и алгоритмов решения уравнения (1),в частности метода несиммстри последовательной верхней релаксации Ньютона (НПВР-Н). Установлен! условия сходимости. Проведены численные эксперименты, подтверждай эффятэнссть предлагаемого метода.

Для системы нелинейных численных уравнений вида (4) га счет вы в общем многоступенчатом метод: га=2,и операторов Ф|(х,у) в вида

И 1 ! т 1

М | | т |

2 1=1+1 2 ♦«-¿-ЬО^-Сь ¿«ТТ.

где

-----------------------

та» тг I ______ ,..

\sfjix)

Получаем сяэдугсгцт! алгоритм

, w t _<»> ,<»>

' („) (п) (SV> + ZV' ЬС')

)«|_J4*l_

t| -t|

(„+D _(n) + +1,(1. )-<:,>

и =ti -ülü-— .¡«i,k,

aB +gj(t, )

где iü, (0^ -числовые параметры. При fi) •» (0^ ьгетод (5) назовем СПВР-Н, а

при СО -НПВР-Н. r I г

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

С помощью предложенных алгоритмов получены численные решения уравнения (5). Методы Ныотона-Канторовцча, хорд, ЭПткепа-Стеффснссна и другие итерационные методы, основанные на "полной" линеаризация, оказываются а этом случае мало' пригодными в силу больших вычислительных затрат, возникающих при реализации их численных аналогов.

Публикации по т еме джусутаниту по теме диссертации опубликовано пять статей [ 1 ]•[ 5 ]. Из них гирвая работа выполнена совместно с научным руководителем, которому принадлежит постановка основной задачи н общая идея es решения. В других работах выполненных в соавторстве, соавтору принадлежат некоторые дополнения, высказанные а ходе обсуждения.

ЬБсльтюков Б.А., Минеева О.В., Черняк ВЛ. Один класс двухступенчатых меюдов тина Ньютона, // В кн.: Приближенные ыетаы анализа и их приложения.' Иркутск: Изд-во СЭИ СО АН СССР, 1985, с.72-81.

2. Минеева О.В., Черняк В.Я. Один метод решения системы нелинейных уравнений. I/ В кн.: Приближенные методы анализ« и их приложения. Иркукк: Изд-во СЭИ СО АН СССР, 1985,с. 130-135.

3. Минеева OB. Oö одном классе двухступенчатых методов lima Ньютоне. Н В кн.: Ч стерта я межвузовская конференция молодых ученых,

Ь '

( Тезисы докладоз ). Иркутск: Изд-ьо Иркутский государственный унивсропгет, 1986, с.27.

А. Кузнецова O.D. О некоторых приложениях многоступенчатого ыеггода типа Ньютона. У/Иркутск, Изд-во НГУ, 1993, с.22-24.

3. Кузнецову О.В., Черняк ВЛ. Один класс многоступенчатых методов типа Ньютона. И В кн.: Приближенные методы решения операторных уравнений. Иркутск; Изд-во Иркутский государственный педяголпеехкй институт, 1992, с. 3-11.