А.А. Самарский - Введение в численные методы (1113832), страница 14
Текст из файла (страница 14)
11онечпо, все эти рассуясдення име!от смысл прп соответствующей гладкости функции /(х). 7. Другие квадратурные формулы. Без нарушеяия общности можно считать у И вЂ” 1 /(х),г. О (о",) Мы рассматривалп до спх пор квадратурпые формулы с заданными узлам~ (.г„): Ух (/) —..- ~~ сх / (х!). (2б) А=-о Зтн формулы точны для всех поликанов степени %. Гслп считать неизвестными не только с„по и узлы хп то х!он!- но требовать, чтобы квадратурная формула (26) была точной для всех полиномов степени 2Ь! — 1. Такая формула называется форврлой Гаусса. Требуя, чтобы для одночлепов 1.
х, г-, ..., х', ..., л' формула была точной. Зная прпближе!шое значение р, можно методом Рунге, изложенным выше, повысить порядок точности. Для зтоь. го образуем комбинацию Х = оУ +(1 — о) Х и выберем о так, чтобы оЬв! + (1 — о) Ь!,' = (о + (1 — о) р") Ь" =- О, т. е. о р"/(р" — 1) = 1/(1 — А). Тогда для погрешности ))" =У' — / получаем ь 3. численное интеГРНРОВлние л 1 1 х ' 1 зп 1-1 Ух[х ] = . С1,хд = ] х 11х т 1-1 1! О е о Рл -=0,1, ...,2Х вЂ” 1, получим для узлов и весов 211!ос 2 уравнений с„+ с, ';-...
+ сл 1, г„х„с с,х, ( ... '- слхл =- 112, и, л! ! сах!! .'; с!т, '- ... + Слх!С == 1'(ьч + 1), с хе .-'; с,г!' -,.'-... —:; Сл.тт! — 1 (У -;- 1). !Л 11, ЛЛЕ1, !Л 1.1 Общее число неизвестных равно 2Ю+ 2, т, е. 11'+ 1 неиз- вестных узлов и )т'+ 1 весовых мноееителей, Число уран- неппй также равно 2111+ 2. Можно доказать, что напи- санная система уравиеш!й имеет решение, Приведем простейшую формулу Гаусса при У 2: Ул (.1) - —,„' 1(..) .
—,"-„1(~,); — '„' !(~1), где х.= ! ! ' .. ! ! Формулы Гаусса дшот хорошую точность прп Небольшом числе узлов. Гще одним примером является евадратурпая формула Чебышева, в которой .выбираются наилучшие узлы в предположении, что все веса равны. В етом случае т УЛ.У) == —,,«~ 1(11) А-1 Требуя, чтобы формула была точной для 1(х) =-х, х".. ..., х', получим Л! уравнешш для определения х„х„, ..., хх: и -,'-1' Зти уравнения имеют решения при т 1, 2, ..., 7, 9, а при т 8 и вт> 10 не имеют вещественных норнен. Зд гл и.
интввполяцня н числкннок инткгшшовэппа 1!рп ш = 3 формула т1ебышева имеет впд ' з~У~ ~ — —,, Ъг 2)+ У(,—., ) -'- у~ —., + —,)г 2)~. й 2) Подыптегральпая функция имеет экспоненцпальный характер: )(х) = се, т. е. функция 1п)(х) линейка. Представим )(х) в виде /(х) =ехр(1п ((х)), проиктерполнруем 1п)(х) линейно па отрезке (х~-„х); )п1(х) = ' !п~;, + ' !пав, Д'~ Х4-1 и затем проинтегрируем по х от х;, до х,. Эта формула оказывается полеаной па практике.
3) Если !'(х) является быстро осциллирующей функцией. так что ее можно ааписать в виде )(х)= у(х) соз ых, где частота ы те 1 велика, то нрп вычислении интеграла можно воспользоваться следующим приемом. Сначала проинтегрируем по частям: ) (х) г(х =- ~ у (х) соз юх г(х- ю-1 =- — у з!и юх ы — — у (х) з!и ых Их. ! р и х; ц-1 Если у(х) — линейная на (х, „х,1 функция, то интеграл справа берется в явном виде. Если у(х) — полипом степени и, то интегрирование по частям производим и раз, для нее коэффициент прп (~/т' ~е в оценке для погрешности в два раз» меньше, чем для формулы Симпсона. Замечания. В ряде случаев вычислению интегралов должно предшествовать пл преобразование, учитывающее специфику подынтегральной функции. !)римеры: )(х) = —,— ~е(х), )„(О)ФО, т. е.
)(х) имеет осое о бенность прп х = О. Эта особенность устраняется заменой переменной: 3 1 1 1 Гла аз 111 ЧИСЛЕННОЕ РЕ!ПЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ В этой главе изучаются методы численного решения систем:шнейных алгебраических уравнений, т. е. численные методы линейной алгебры. Существуют два тина методов — прямые н итерационные. Иы рассматриваем прежде всего метод исключения Гаусса для систем общего вида п варианты — метод прогонки и методы матричной прогонки для систем специального вида (с трехдлагональной плп блочпо-трехдпагопальной матрицами). ')то — прямые .нетодьь Их эффективность зависит от порядка системы н структуры матрицы.
Прн изучении нгерпционнььг методов мы трактуем спетому уравнений как операторное уравнение первого рода Аи=)' п излагаем общую теорию итерационных методов для операторных уравнений при минимальных предположениях отяосительло оператора А, Общая теория позволяет доказать сходпмость итераций для метода Зейделя п метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая. когда известны границы у, ) О н у. ,~ т, спектра оператора А в некотором энергетическом пространстве П ; 2) для случая, когда границы т, и у, неизвестны. (Зесьма зффектнвпым является попеременно.треугольный метод, который изучается в 1,ь й 1.
Системы линейных алгебраических уравнений 1. Системы уравнений, Основная задача линейной алгебры — решение системы уравнений Ап=), (1) где и= (и"', ..., и"') — искомый вектор, ) = ()'о, ~'",... Г"з) — известный вектор размерности ))), А =-(а„) (ю', ) = 1, 2.. . Ю) — квадратная матрица размера )() Х Л' с элементами аь. Будем предполагатгь что матрица А невырождева; бе(А чьО, так что уравнение Ам =О имеет только тривиальное решение, и система (1) имеет единственное ян Гл. (и.
Рь(панне Алгенгхичеспих углзиений решенне а„и'о =/'", откуда находим и" =у(о/п,ь 1- 1, 2, ..., Ж. Если Л вЂ” яиясляя треугольная глптрийп, т, г. пп — — О прп у ) ( (у, у — 1, 2...., Ю), п„ч" О, а о ... о 1м 1.„0 ах ах,...а. то система уравнений имеет впд а ион 1( а и"'+ п.,и( ~ г(, гг (н у(гу анги т. пят(г' +... , 'пляи ' у' ° (1( (м (х( яя( В курсе линейной алгебры решение системы (1) обычно выражают по формулам Крамера в виде отношений определителей. Для численного решепвя системы (1) эти формулы непригодны, так как они требуют вычисления %+1 определнтелен, что требует большого числа действий (порядка М арифметических операций).
Да'ке прп зыборе наилучшего метода вычнсленпе одного определителя требует примерно такого же времени, что н решение системы линейных уравнений современными численными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к большим опгкбкам округлений. Особенность болыпипства численных методов для (1) состоит в отказе от нахождения обратной матрицы. Основное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решенкя с заданной точностью е ) О (экономичность численного метода), 2. Частные случаи систем.
Несложно репшть систему (1) в перечнсяенныт виже частных случаях. Пусть матрона А — дипгояпяьяпя, т. е. п„=-О, уяь У, оьФО ((, у- 1, 2, ..., Л'). Тогда система имеет впд ОО ГЛ. П!, РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ УРАВНГНИИ вЂ” — с, ь,о...о а„— с ь,,...о А —— о О сп — сн Соответствующая система (1) имеет впд (1), (Ю вЂ” си +Ьи (о с — и(') -(- Ь ани ' — они ' = ~п, (и-и (н) 1 = 2, 3, ..., Л' — 1. Это разностпое уравнение второго порядка, которое мы рассматривали в гл.
1, где для его решения применялся метод прогонки. 3. Операторное уравнение первого рода. Известно, что всякая матрица А = (оо) О, )'=1, 2, ..., Ж) определяет линейный оператор А, отображающий пространство Нн в себя: АиыН~ для любого и(ИН~ плп А: Нн- Н". Обратно, каждому оператору А (в некотором бааисе $~, .... 3н) соответствует матрица А = (ас) размера УХ)((, где ае — компонента вектора А3). Поэтому мы можем рассматривать (1) как операторное уравнение первого рода Нн (3) с оператором А: Н» — Н'.
Чтобы подчеркнуть эквивалентность задач (1) и (3), мы сохраним о)(по и то же обозначение А кан для мат- по вышсляются по заданным формулам, и их моя(яо не хранить в оперативной памяти машины. Это очень важ. но, так как порядок таких матриц может достигать не. скольких десятков и даже сотен тысяч. Частным случаем разреженной матрицы является ленточная натри()а; все ее ненулевые элементы находятся вблизи главной диагонали, т. е. а,)=0, если )1 — у) >1 где 1(М. Отличные от нуля элементы расположены на 21+1 диагоналях, включая главную диагональ. Примером является трехдиагональная матрица Ф ь систкмы Алгевгличкскпх угхвнкнии 89 рицы, так и для оператора. Индекс У у Нв будем опускать н писать просто Н.
Переход от (1) к операторному уравнению удобен для изложения теории итерационных методов. Прп етом какая-либо конкретная информация о структуре матрицы А не используется. В пространстве Р введем скалярное произведение (,) и норму зи! = У ~~, и). Будем предполагать, что оператор А является самосопряженным и положительным: А = А*>0. Будем рассматривать также знергетические пространства Но со скалярным произведением (и, и)о = (Ра, и) и нормой 1л1в= У(Ри, и), где Р— линейный самосопрнженный положительный оператор: Р: Н Н, Р = Р* > О.
Обозначим через ($„Л.) (в = 1, 2, ..., Ж) собственные векторы н собственные значения оператора А: А", ).,с,. („, $„,) = б,.„„в, т = 1, 2, ..., У. Так как А > О, то )., >О, и можно счнтать, что 0 с)., -'-= < )., <... - ),х, а значит, справедливо неравенство ')„Г с А ~ лхГ, )., = пйи ).„Хх = шах), Отношение два, называют числом обусловленности.
На практике удобнее пользоваться обратным отношением, т. е. параметром $=).,l).,;, который мы будем называть мерой обусловленности, От него„как зто будет показано ниже, зависит скорость сходимостп итераций. Параметр $ для разностных уравнений, аппрокспмирую1цпх уравнения математнческои физики (например, уравнения Лапласа), мал: с = 10 ' — 10 ' (число обусловленности велико). Из формулы и = А ') вкдно, что 1Ч~ 11 1 Ис ')то неравенство выражает устончпзость решения задачи (1) по правой части. Если 1А Ч =-1Й, очень велико, то задача (3) может оказаться некорректной, т.
е. неустойчивой по отношению к ошибкам в задании правой части, в том числе к ошибкам округления. 4. Прямые и итерационные методы. Численные методы решения системы (1) условно разбивают н» две группы, выделяя прямые и итерационные методы (имеются, конечно, и гибридные методы). Прямые методы позволяют за конечяое число действий получить точное решение 90 гл и!. Решвние х,чгввгхнческих >Рзангннп системы уравпепнй, если входная информация (правая часть уравнення 1 п элементы ае матрицы Л) заданы точно и вычнстенпя ведутся без округления. Простейший пример прямого метода — метод прогонкн. Конечно, прямые методы также дают решеняе с определенной точностью, которая завпснт от о>пибок округтепия, т.
е. от ма>пины, и от характера вычислительной устойчивости, что зависит от самого метода. 11теро>(ио»ны>1 метод позволяет найти приближенное реп>онне спстемы путем построения последовательности прпближепий (итераций), пачнпан с некоторого начального ориблп;кения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
