Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 7
Текст из файла (страница 7)
Однако напрактике его приходится подбирать экспериментально методом проб и ошибок,поскольку найти λmin и λmax с достаточной точностью удается в редких случаях.Задача 4Построить приближенное решение системы (112) методом верхней релаксации,полагая ω = 4 / 3 .11⎞⎛Выпишем для рассматриваемого случая матрицыD + TH и ⎜1 − ⎟ D + TB ,ω⎝ ω⎠определяющие итерационный процесс:- 29 ⎡3/ 4 0 ⎤ 1⎡1/ 4 1 ⎤3D + TH = ⎢,D+T=B⎥⎢ 0 1/ 2 ⎥ .4⎣ 1 3/ 2 ⎦ 4⎣⎦С их помощью рекуррентное соотношение (123), записанное покомпонентно,принимает вид:3 k +1 1 kx1 + x1 + x2k = 0,4431x1k +1 + x2k +1 + x2k = 1.22k +1Выражая из первого соотношения x1 , из второго x2k +1 , получим окончательныерасчетные формулы для компонент очередной итерации:14x1k +1 = − x1k − x2k ,332 21x2k +1 = − x1k +1 − x2k .3 33Примем, как и в предыдущих случаях, за начальное приближение нулевой вектори сделаем три итерации.
При этом для каждой из них подсчитаем невязку (71),позволяющую следить за сходимостью процесса5⎧ 2⎫⎧2 1⎫≈ 0.745 ,x1 = ⎨0, ⎬ , ψ1 = ⎨ , ⎬ , ψ 1 =3⎩ 3⎭⎩3 3⎭41⎧ 8 28 ⎫⎧4 5⎫≈ 0.237 ,x2 = ⎨− , ⎬ , ψ 2 = ⎨ , ⎬ , ψ 2 =27⎩ 9 27 ⎭⎩ 27 27 ⎭895 ⎫⎧ 88 256 ⎫⎧ 8≈ 0.039 .x3 = ⎨− ,,⎬ , ψ 3 = ⎨−⎬ , ψ3 =243⎩ 81 243 ⎭⎩ 243 243 ⎭Поведение невязок, а также сравнение членов итерационной последовательности x k сточным решением системы x = {−1,1} показывают сходимость процесса, болеебыструю, чем в методе Зейделя.
Выбранное значение параметра ω = 4 / 3 оказалосьблизким к оптимальному ω = ω* .- 31 -Глава 2. ЧИСЛЕННОЕ РЕШЕНИЕ УРАВНЕНИЙВ школьном курсе математики изучают линейные и квадратные уравнения,корни которых могут быть найдены по известным формулам. Существуют такжеформулы для решения уравнений третьей и четвертой степени, однако они сложны инеудобны для практического применения. На их обсуждении мы останавливаться небудем.
Если рассматривать неалгебраические уравнения, то задача усложняется ещебольше. В этом случае получить для корней ответ в виде формул, за редкимисключением, не удается.В условиях, когда формулы «не работают», когда рассчитывать на них можнотолько в самых простейших случаях, важное значение приобретают универсальныевычислительные алгоритмы. Их много и они достаточно разнообразны. Если записатьуравнение в видеf ( x) = 0 ,(1)то эти алгоритмы обычно не накладывают никаких ограничений на конкретный видфункции f ( x) , а предполагают только, что она обладает свойствами типанепрерывности, дифференцируемости и т. д.В этой главе мы познакомимся с тремя алгоритмами. Они основаны на разныхидеях, каждый из них обладает определенными достоинствами и недостатками,поэтому в конце главы будет интересно сравнить алгоритмы между собой.§1. Метод вилки.
Теорема о существовании корня непрерывнойфункции.Метод вилки и его применение к доказательству фундаментальной теоремы осуществовании корня у функции f ( x) , непрерывной на отрезке [ a, b ] и принимающейна его концах значения разных знаков, подробно разбирается в курсе математическогоанализа. Несмотря на это мы конспективно изложим его вновь, поскольку без методавилки картина численного решения уравнений была бы неполной.Теорема о существовании корня непрерывной функции.Если функция f ( x) непрерывна на отрезке [ a, b ] и принимает на его концах значенияразных знаков, то на этом отрезке существует по крайней мере один кореньуравнения (1).Предположим для определенности, что функция f ( x) принимает на левомконце отрезка [ a, b ] отрицательное значение, на правом – положительное:f (a) < 0 , f (b) > 0 .(2)Возьмем на отрезке [ a, b ] среднюю точку ξ = ( b − a ) / 2 и вычислим в ней значениефункции f (ξ ) .
Если f (ξ ) = 0 , то утверждение теоремы доказано: мы нашли наотрезке [ a, b ] точку c = ξ , в которой функция f ( x) обращается в ноль. При f (ξ ) ≠ 0поступим следующим образом: рассмотрим два отрезка [ a,ξ ] и [ξ ,b ] и выберем одиниз них, исходя из условия, чтобы функция f ( x) на его левом конце была- 32 отрицательной, на правом – положительной. Выбранный отрезок обозначим [ a1 , b1 ] .По построениюf (a1 ) < 0 , f (b1 ) > 0 .Повторим описанную процедуру: возьмем на отрезке [ a1 , b1 ] среднюю точкуξ1 = ( b1 − a1 ) / 2 и вычислим в ней значение функции f (ξ1 ) .
Если f (ξ1 ) = 0 , тодоказательство теоремы закончено. Если же f (ξ1 ) ≠ 0 , то снова рассмотрим дваотрезка [ a1 ,ξ1 ] и [ξ1 ,b1 ] и выберем тот, на левом конце которого функция f ( x)отрицательна, на правом – положительна. Выбранный отрезок обозначим [ a2 , b2 ] . Попостроениюf (a2 ) < 0 , f (b2 ) > 0 .Будем продолжать этот процесс. В результате он либо оборвется на некоторомшаге n в силу того, что f (ξ n ) = 0 , либо будет продолжаться неограниченно. В первомслучае вопрос существования корня уравнения (1) решен, поэтому нам нужнорассмотреть второй случай. Неограниченное продолжение процесса даетпоследовательность отрезков [ a, b ] , [ a1 , b1 ] , [ a2 , b2 ] , … . Эти отрезки вложены друг вдруга – каждый последующий отрезок принадлежит всем предыдущим:an ≤ an+1 < bn+1 ≤ bn ,(3)причемf (an ) < 0 , f (bn ) > 0 .(4)Длины отрезков с возрастанием номера n стремятся к нулю:b−alim ( bn − an ) = lim n = 0 .(5)n →∞n→∞ 2Рассмотрим левые концы отрезков {an } .
Согласно (3) они образуют монотоннонеубывающую ограниченную последовательность. Такая последовательность имеетпредел, который мы обозначим через c1 :lim an = c1 .(6)n→∞По теореме о переходе к пределу в неравенствахc1 ≤ bn .(7)Теперь рассмотрим правые концы отрезков {bn } . Они образуют монотонноневозрастающую ограниченную последовательность, которая тоже имеет предел.Обозначим этот предел через c2 :lim bn = c2 .(8)n→∞Согласно соотношениям (3), (6), (7), (8) пределы c1 и c2 удовлетворяют неравенствамan ≤ c1 ≤ c2 ≤ bn ,и, следовательно,b−ac2 − c1 ≤ bn − an = n .(9)2- 33 Таким образом, разность c2 − c1 меньше любого наперед заданного числа. Этоозначает, что c2 − c1 = 0 , т.
е.c2 = c1 = c .(10)Найденная точка c интересна тем, что она является единственной общей точкойдля всех отрезков построенной последовательности. Используя непрерывностьфункции f ( x) , докажем, что она является корнем уравнения (1).Мы знаем, что f (an ) < 0 . Согласно определению непрерывной функции ивозможности предельного перехода в неравенствах имеемf (c) = lim f ( an ) ≤ 0 .(11)n →∞Аналогично, учитывая, что f (bn ) > 0 , получаемf (c) = lim f ( bn ) ≥ 0 .n→∞Из (11) и (12) следует, что(12)f (c ) = 0 ,(13)т.
е. c – корень уравнения (1). Теорема доказана.Процесс построения последовательности вложенных стягивающихся отрезковметодом вилки является эффективным вычислительным алгоритмом решенияуравнения (1). На n -ом шаге получаемan ≤ c ≤ bn .(14)Это двойное неравенство показывает, что число an определяет искомый корень c снедостатком, а число bn - с избытком, с ошибкой, не превышающей длину отрезка[ an , bn ] . При увеличении n ошибка стремится к нулю по закону геометрическойпрогрессии со знаменателем q = 1/ 2 . Если задана точность ε , то, чтобы ее достигнуть,достаточно сделать число шагов N ,удовлетворяющее условиюb−aN > log 2.(15)εТо, что процедура отыскания корня основана на многократном делении исходногоотрезка пополам, оправдывает второе название метода – метод бисекции.Теорема и метод ее доказательства сами по себе не позволяют определить общеечисло корней функции f ( x ) на отрезке [ a, b ] .
Однако, если функция f ( x) не тольконепрерывна, но и дифференцируема, то дополнительное ее исследование с помощьюпроизводной может во многих случаях решить и этот вопрос. Например, в случаезнакоопределенной производной функция f ( x) является монотонной на отрезке [ a, b ] ,так что корень у нее может быть только один.Задача 1.Рассмотреть на отрезке [ a, b ] уравнениеf ( x) = x − cos x = 0 .(16)Показать, что оно имеет единственный корень и найти его приближенное значение спомощью метода вилки.В данном случае- 34 -f (0) = −1 < 0 , f (1) = 1 − cos1 > 0 ,(17)f ′( x) = 1 + sin x > 0 , при 0 ≤ x ≤ 1 .(18)Неравенства (17) говорят о том, что уравнение (16) имеет корни. Условиемонотонности функции f ( x) (18) означает, что корень единственный.
Результаты,связанные с 12-кратным делением отрезка [ 0,1] пополам даны в таблице 1. Ониопределяют корень с точностью ε = (1/ 2 ) < 0.00025 . Искомый корень c принадлежитотрезку[0.739013671875, 0.739257812500]Отбрасывая знаки, лежащие за пределом достигнутой точности, получим0.73901 < c < 0.73926График функции (16), иллюстрирующий разобранный пример, приведен на рис. 1.12Таблица 1.n0123456789101112an0,0000000000000,5000000000000,5000000000000,6250000000000,6875000000000,7187500000000,7343750000000,7343750000000,7382812500000,7382812500000,7382812500000,7387695312500,739013671875bn1,0000000000001,0000000000000,7500000000000,7500000000000,7500000000000,7500000000000,7500000000000,7421875000000,7421875000000,7402343750000,7392578125000,7392578125000,739257812500ξ n = ( an + bn ) / 20,5000000000000,7500000000000,6250000000000,6875000000000,7187500000000,7343750000000,7421875000000,7382812500000,7402343750000,7392578125000,7387695312500,739013671875f (ξ n )-0,3775825618900,018311131126-0,185963119505-0,085334946152-0,033879372418-0,0078747254590,005195711744-0,0013451497520,0019238727810,000289009147-0,000528158434-0,000119596671§2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
