Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 99
Текст из файла (страница 99)
Часто из двух методов, в одном нз которых проще вычислительная схема, но требуется большее число злключвннв б)З вычислительных операций, чем з другом, слелует предпочесть первый. Однако в задачах, связанных с матрицами высоких порядков, критерий минимальности числа вычислительных операций может оказаться решающим. Сравнение методов по критериям простоты вычислительной схемы, загрузке памяти, приспособленности к индивидуальным особенностям задачи я серийности не представляет труда. Учет количества вычислительных операций тоже не сложен как в точных методах, так и в итерационных, если заранее известна быстрота сходимости. Значительно сложнее опенивать методы по критерию наде>кностгь По сути дела, при приближенной постановке вычислительных задач в нх решении всегдз имеется неопределенность з исходных данных.
Эта неопределенность может быть аначительной, например, при решении плохо обусловленной системы. Численный метод должен считаться належным, если при его применении решение получается с погрешностью, не превосходящей существенно указанной выше неизбежной погрешности. обусловленной неопределенностью исходных данных. Основными факторами, снижающими надежность метода, являются ошибки, происходящие от округления в промежуточных вычислениях. Таким образом, строгий учет надежности должен основываться на оценке влияния ошибок округления.
Практически интересными являются вероятностные оценки, так как оценки „на максимум" почти всегда практически завышены, в силу малой вероятности их реализации. В литературе имеется довольно иного рабо~, посвященных исследованию влияния ошибок округления в основнгях арифметических операциях и в некоторых численных методах линейной алгебры. Сюда относятся работы: Нейман и Голдстайн [1), Тюрннг [1), Голд- стайн и Нейман )1), Дуайр н Уо )1), Абрамов [2), [3), Хаусхольдер )3), [11), Голдстайн, Ыеррей и Нейман [1), Карр )1) и др. В частности, детальному анализу подвергнута Нейманом н Голдстайном схема главных элементов Гаусса.
Однако в настоящее время далеко не все основные методы подвергнуты такого рода исследованию. Волее того, нногдз такое исследование оказывается принципиально невозможным, в силу зависимости влияния ошибок округления от факторов, которые заранее нельзя учесть. Так, при проведении схемы единственного деления при решении системы линейных уравнений с ззранее фиксированным порядком исключения неизвестных, надежность результата определяется в значительной степени тем, будет лн происходить уничтожение значащих цифр по холу процесса или нет, что, в свою очередь, зависит от существования или несуществования малых главных миноров у матрицы коэффициентов.
Для одной и той же системы может оказаться, что при различном выборе порядка исключения неизвестных различной будет и надежность результата. Наиболее надежным будет выбор порядка исключения, совпадающий с порядком в схеме главных 614 ВАключение элементов. Таким образом, схема единственного деления с фиксированным порядком исключения неизвестных оказывается не безусловно надежным методом и во всяком случае менее надежным, чем схема главных элементов. Однако отсюла еще не следует, что схема главных элементов всегда предпочтительнее, так как ее реализация значительно сложнее, чем реализация схемы с фиксированным порялком исключения. Многие другие численные методы линейной алгебры оказываются не безусловно надежными.
Такими оказываются биортогональный алгорифм и метод минимальных итераций. Их надежность зависит зо многом от удачного выбора начального вектора. Среди методов определения собственных значений наиболее надежными являются те, в которых собственные значения определяются минуя вычисление коэффициентов характеристического полинома, так как незнзчнтельные ошибки в определении этих коэффициентов мокнут повлечь значительные ошибки в вычислении корней. Но вместе с тем итерационные методы для решения полной проблемы собственнь:х значений оказываются значительно более трудоемкими, чем точные, связанные с вычислением коэффициентов характеристического полинома.
Нам представляется, что в оценке применимости не безусловно надежных методов основное значение имеет опыт нх использования и лишь по мере обобщения этого опыта будет возможно высказать более определенные суждения по этому вопросу. Скажем еще о некоторых приемзх, повышающих належность методон. Теоретически говоря, каждый „точный" метод линейной алгебры имеет в себе неограниченный запзс надежности, который может быть резлизован за счет точности проведения промежуточных вычислений. Значительное повышение точности на всем протяжении вычислительного процесса часто оказывается невозможным, и повышение точности следует применять в наиболее „уязвимых" ситуациях. Источником значительных ошибок от округления является н вычисление сумм произведений ~ алба с округлением до данного а=1 количества цифр в каждом слагаемом.
Эту операцию часто целесообразно проводить с д в о й н о й т о ч н о с т ь ю, вычисляя каждое .слагаемое без округления и отбрасывая лишние знаки после выполнения сложения. Конечно, применение двойной точности иногда оказывается излишним, например, при проведении самоисправляющегося итерационного процесса. При пользовании не безусловно надежными методами часто может быть целесообразно проводить алгорнфм в двух неэквивалентных вариантах; например, проводить схему единственного деления при двух выборах порядка исключения неизвестных; применять биортогональный алгорифм исходя нз двух начальных векторов н т. д.
Неплохой косвенной проверкой надежности вычислений может служить применение контролей по холу процесса. ДОПОЛНВНИВ АР,=Л; Р'Л =Р тАР ==А,; АРз=Л; Р'Л =Р 'А,Р =А,; Аа,Ра = Лги Р' 1.„= Р„г А,Р„= А,; Здесь Р, ортогональные матрицы, Лг левые треугольные. Матрицы Р, могут быть вычислены, например, как произведения матриц вращения или матриц отражения, подобно тому, как это делалось в й 16 прн решении линейных систем. Покажем, что последовательность матриц А„ сходится к диагональной матрице, составленной из собственных значений ма~рицы А, расположенных в порядке убывания модулей, а матрица 0 =Р, ...
Рд при достаточно большем л имеет столбцы сколь у~одно близкие к нормированным собственным векторам матрицы А. Для доказательства установим связь процесса с 1.1т-алгорифмом, примененным к матрице А'. Имеем Л Л' = — АР Р'А = А' Л'Л =Р'А'Р = Аз =Л Л,' 1 1 т т 1 3 а ЛаЛа = — Р;Аа,Р, =- А', = Ла„,Л; „ Л! диагональная матрица, составленная из диагональных Лп Положим есть левая треугольная матрица с единичной днагоа Йа есть правая треугольная матрица с диагональю Лз Пусть элементов Ясно, что налью, а Изложим еще один итерационный процесс для решения полной проблемы собственных значений, сообщенный авторам В.
Н. Кублановской. Процесс заключается в следующем. Пусть матрица А симметрична и ее квадрат не имеет кратных собственных значений, Строим последовательность матриц 616 дополнении Легко проверяется, что Е,)1, =. А' и 11а ,Еа , = Е,Я», т. е. мзтрицы Е, и 11, совпадают с одноименными матрицами Е11-алгорифма, примененного к матрице А'.
Ввиду того, что мзтрица А' положительно определена и ее собственные значения попарно различны, Ы-алгорнфм для нее сходится, в частности, диагональные элементы матриц Й» сходятся к квадратам собственных значений матрицы А. Следовательно, бр Рд — — бр Ла -+ Вр А'. Далее, положив Ла=(1г а), имеем бр А = БрАа=5рЛаХ~=~~'.,1да= к1 з з в, з з к~1н,а+ 2 1гда ВРЛа+ Х~ Ьа' г г>1 г >/ Поэтому, при н-ьсю, ~ 1еьа — +О, так что все недиагональные а г>1 элементы матрицы Л стремятся к нулю. Следовательно, А' =. Л'Ла -+ [)а, ..., ),а) при Уг — + оо. Матрицы Аз при достаточно больших й становятся сколь угодно близкими к диагональным матрицам (~), „+ Л„]. Но так как матрицы Аа при всех Л подобны матрице А, то Аа -+ [Л,, ..., ),„3. Далее, Аз=С>„'А1)а и, следовательно, при достаточно большом й столбцы матрицы 1)а сколь угодно близки к собственным векторам матрицы А, нормированным, в силу ортогональности 1) .
В силу неоднозначности выбора матриц Рд, последовательность матриц ф, может не быть сходящейся. Она будет сходящейся лишь с точностью до знаков столбцов. Сходимость будет иметь место, если, начиная с некоторого местз, брать на каждом шагу матрицу Ра возможно более близкой к единичной. Процесс позволяет использовать для ускорения сходимости как сдвиги (подобно Ей-алгорифму), так н уточняющие формулы метода Якоби.
ЛИТЕРАТУРА А б р а м о в А. А. [Ц Ускорение сходимости в итеративных процессах, Докл. АП СССР, 1950, 74, 1051 — 1052; М. й., 12, 861. (2) О влиянии ошибок округления при решении уравнения Лапласа. Вычисл. матем. и вычисл. техника, 1953, 1, № 1, 37 — 40; М. й., 16, 1156.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
