Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 14
Текст из файла (страница 14)
! р Ю х; ц-1 Если у(х) — линейная на (х, „х,1 функция, то интеграл справа берется в явном виде. Если у(х) — полипом степени и, то интегрирование по частям производим и раз, для нее коэффициент прп (~/т' ~е в оценке для погрешности в два раз» меньше, чем для формулы Симпсона. Замечания.
В ряде случаев вычислению интегралов должно предшествовать пл преобразование, учитывающее специфику подынтегральной функции. !)римеры: )(х) = —,— ~е(х), )„(О)ФО, т. е. )(х) имеет осое о бенность прп х = О. Эта особенность устраняется заменой переменной: 3 1 1 1 Гла аз 111 ЧИСЛЕННОЕ РЕ!ПЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ В этой главе изучаются методы численного решения систем:шнейных алгебраических уравнений, т.
е. численные методы линейной алгебры. Существуют два тина методов — прямые н итерационные. Иы рассматриваем прежде всего метод исключения Гаусса для систем общего вида п варианты — метод прогонки и методы матричной прогонки для систем специального вида (с трехдлагональной плп блочпо-трехдпагопальной матрицами). ')то — прямые .нетодьь Их эффективность зависит от порядка системы 0 структуры матрицы. Прн изучении нгерпционнььг методов мы трактуем спетому уравнений как операторное уравнение первого рода Аи=)' п излагаем общую теорию итерационных методов для операторных уравнений при минимальных предположениях отяосительло оператора А, Общая теория позволяет доказать сходпмость итераций для метода Зейделя п метода верхней релаксации при минимальных ограничениях на оператор А.
Рассмотрены два класса методов: 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А 1= Ио ')то неравенство выражает устончпзость решения задачи (1) по правой части. Если 1А Ч =-1Й, очень велико, то задача (3) может оказаться некорректной, т. е. неустойчивой по отношению к ошибкам в задании правой части, в том числе к ошибкам округления. 4. Прямые и итерационные методы. Численные методы решения системы (1) условно разбивают н» две группы, выделяя прямые и итерационные методы (имеются, конечно, и гибридные методы). Прямые методы позволяют за конечяое число действий получить точное решение 90 гл и!.
Решвние х,чгввгхнческих >Рзангннп системы уравнепнй, если входная информация (правая часть уравнення 1 п элементы ае матрицы Л) заданы точно и вычнстенпя ведутся без округления. Простейший пример прямого метода — метод прогонкн. Конечно, прямые методы также дают решеняе с определенной точностью, которая завпснт от о>пибок округтепия, т. е. от ма>пины, и от характера вычислительной устойчивости, что зависит от самого метода. 11теро>(ио»ны>1 метод позволяет найти приближенное реп>онне спстемы путем построения последовательности прпближепий (итераций), пачннан с некоторого начального нриблп;кения. Само приближенное решение явлнется результатом вь>чпс,>епп», полученным после конечного числа птерацпй.
Выбор того нлп нного чнслешни.о метода завнспт от многнх обстоятельств — от имеющихся программ, от вода матрицы А, от тнпа расчета п др. Пояс>шм слова «тпп расчетаз. Возможны разные постановки задачн: 1) найти решение одной конкретной задачи (1); 2) найти решение песколькпх варпантоз задачи (1) с одной и той жо матрпцей А и разнымп правымп чзстямп 1. Может оказаться, что пеоптнмальпый длл одной задачи (1) метод является весьма эффективным для многоварпантного расчета.
Прп многовариантном расчете можно уменьшить среднее число операций длн одш>го варианта, если хранить некоторые величины, а пе вычнслять пх заново для каждого варианта. Ото, конечно, зависит от машины, от объема ее оператнвпой памяж>, 11з сказанного ясно, что выбор алгорнтма должен зависеть от тапа расчета, от объема оперативной памяти машины и, конечно, от порядка системы. Качество алгоритма определнется тем машинным временем, которое требуется для нахождения решеппв сметены (1). Естественно выбирать тот метод, для которого время реп>ения минимально по сравнению с другнмп методамп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
