Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 25
Текст из файла (страница 25)
Необходимо лишь прервать итерационный процесс в тот момент, когда приближения окажутся в опасной близости к интервалу неопределенности. Один из способов заметить этот момент состоит в использовании правила Гарвика (см. 8 4.2).— Отметим, что при попадании очередного приближения в малую окрестность решения теряет устойчивость и метод Стеффенсена. $4.8. Дополнительные замечания 1. Метод обратной квадратичной интерполяции. Пусть приближения х1и г1, х1" 11, х'"1 уже найдены, а соответствующие значения функции 1 различны (последнее предположение заведомо будет выполнено, если функция г строго монотонна).
Тогда строят такой квадратичный многочлен Рг(у) от переменной у, что х'" = Рг(1(х'")) для 1 = п — 2; и — 1, и. За очередное приближение к решению принимается х1 "" ' = Рг(0). Этот трехшаговый метод обладает локальной сходимостью с порядком р ~ м 1.839; для начала его работы требуется задание трех хороших начальных приближений. 2.
Методы с порядком сходимости вьппе второго. Приведем пример одношагового метода, обладающего кубической сходимостью: Существуют и другие методы с порядком сходимости выше второго, теоретически очень быстро сходящиеся вблизи корня. Однако они редко используют- 120 ся на практике, так как их преимущество в скорости сходимости начинает проявляться лцшь тогда, когда итерации уже почти сошлись и в действительности осталось сделать 1 — 2 итерации либо вообще пора прекратить вычисления. Чтобы ощутить преимущество таких методов над методами Ньютона и секущих, нужна ЭВМ с очень высокой разрядностью и желание получить решение с чрезвычайно высокой точностью.
3. Вычисление корней многочленов. Вычисление корней многочленов Р„(х) степени гг — специальная задача, для решения которой разработано большое число эффективных алгоритмов. Укажем на один из них — лгег>год Мюллера. В нем по трем ранее найденным приближениям т> " 2', х' " > >, г' "> строят интерполяционный многочлен второй степени Я~(х), т.
е. такой многочлен для которого Я~(х>") = 1(х>'>) при г' = и — 2, гг — 1, гг. За очередное приближение х> "+>> принимают тот из двух корней многочлена Я~(г) (в общем случае являющихся комплексными), который расположен ближе к г' "' . Вплоть до начала 60-х годов задача вычисления корней многочленов была весьма распространенной. Одна из основных причин состояла в том, что к отысканию корней характеристического многочлена сводилась одна из важней— ших задач алгебры — задача вычисления собственных чисел матриц.
В настоящее время существуют другие, гораздо более эффективные численные методы вычисления собственных значений (см. гл. 8), и, по-видимому, задача вычисления корней многочлена во многом потеряла свою актуальность. Как было отмечено ранее, к задаче отыскания корней многочлена высокой степени с приближенно заданными коэффициентами следует отнестись очень внимательно: она может оказаться плохо обусловленной (см. в гл. 3 пример Уилкинсона). Вообще, можно посоветовать избегать применения методов реше— ния вычислительных задач, в которых используются многочлены высокой степени. 4.
Гибридные алгоритмы. В последние годы получили признание алгорит— мы, которые называют гггбрггдггыли (или регуляризированнылги). Они представляют собой комбинации надежных, но медленно сходящихся методов типа бисекции с недостаточно надежными, но быстро сходящимися методами типа секущих и Ньютона. Результирующие алгоритмы обладают высокой надежностью и гарантированной сходимостью. В тех же случаях, когда в окрестности простого корня функции 1 — гладкая, сходимость становится сверхлинейной. Алгоритм ХЕВО1Х, изложенный в 186), является примером эффективного гибридного алгоритма, на каждом шаге которого принимается решение о том, какой из трех методов: бисекции, секущих или обратной квадратичной интерполяции — следует использовать для вычисления очередного приближения.
5. Критерии окончания. Проблема выбора правильного критерия окончания итерационного процесса часто оказывается достаточно сложной. Следует иметь в виду, что наряду с обсуждавшимся в предыдущих параграфах условием /.г' гг> — т~ гг ~> ~ < 6> нередко используется следующее условие: !1 (г'гг>) / < 62. 121 Глава 5 ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИИ з 5.1.
Постановка задачи + а1вха = 61, + агфа аг~ + азха = аЗ, а11х1 + а1гхг+ а1ЗхЗ+ ". а21х1 + аггхг + агзхз + ". а31х1 + аЗгхг + аЗЗхЗ+ .-. (5.1) ащ1х1 + ащгхг + аудзхз + ... + аайКв = 5т. В матричной форме записи эта система принимает вид (5.2) где 61 Ьг ь а11 а12 а13 ... а1 и а21 а22 а23 "- ага аЗ1 аэг аЗЗ .. аэа х= аа1 ааг абаз " ааа В вычислительной линейной алгебре выделяют четыре основные задачи: 1) решение систем линейных алгебраических уравнений; 2) вычисление определителей; 3) нахождение обратных матриц; 4) определение собственных значений и собственных векторов. Задачи 2 и 3 обсуждаются в ~ 5.б, последней по цорядку (но не по значению) задаче 4 посвящена гл. 8. В основном же данная глава посвящена задаче 1, а более точно— прямым методам решения систем линейных алгебраических уравнений с вещественными коэффициентами: Итерационные методы решения системы (5.1) будут рассмотрены в гл.
6. Уделим основное внимание задаче вычисления вектора х, являющегося решением системы (5.2), по входному данному — вектору Ь. Будем предполагать, что матрица А задана и является невырожденной. Известно, что в этом случае решение системы существует, единственно и устойчиво по входным данным. Это означает, что рассматриваемая задача корректна. Хотя задача решения системы (5.1) сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Как будет видно из дальнейшего изложения, значительная часть численных методов решения различных (в особенности — нелинейных) задач включает в себя решение систем (5.1) как элементарный шаг соответствующего алгоритма. Пусть х* = (х~, х.', ..., х*)т — приближенное решение системы (5.1).
В этой и следующих главах мы будем стремиться к получению решения, для которого погрешность е = х — х' мала (количественные характеристики "величины" погрешности будут введены в следующем параграфе). Тем не менее заметим, что качество полученного решения далеко не всегда характеризуется тем, насколько мала погрешность х — х'. Иногда вполне удовлетворительным является критерий малости неаязхи г = 6 — Ах*. Вектор г показывает, насколько отличается правая часть системы от левой, если подставить в нее приближенное решение.
Заметим, что г = Ах — Ах' = А(х — х*) и поэтому погрешность и невязка связаны равенством (5.3) е = х- х* = А 'г. $5 2. Нормы вектора и матрицы — х*)т также являются элементами пространства В". Для того чтобы анализировать методы решения систем, необходимо уметь количественно оценивать "величины" векторов х* и х — х', а также векторов е и 123 1. Норма вектора.
Решением системы линейных алгебраических уравнений является вектор х = (х1, х2, ..., х~)т, который будем рассмат— ривать как элемент векторного пространства Я". Приближенное решение х* = (х*, х', ..., х*)т и погрешность е = х — х = (х1 — х, ..., х~— Ь вЂ” Ь*, где Ь' = (Ь,*, б*, ..., Ь*)т — вектор приближенно заданных 11Х111=Е 1Х11, 11Х112=(Х 1х~1') ', 11Х11 = ПИХ 1Х~1 1( 1'~т (5.4) Первые две из них являются частными случаями более общей нормы: (5.5) (при р = 1 и р =2), а последняя, как можно показать, получается из нормы (5.5) предельным переходом при р ~ 3 а и е ч а н и е 1. Норма 11х112 является естественным обобщением на случай т-мерного пространства понятия длины вектора в двухи трехмерных геометрических пространствах.
Поэтому ее называют евклидовой нориой. 3 а м е ч а н и е 2. Справедливы неравенства 11х11 ( 11х112 ( 11х111( т11х11„, (5.6) указывающие на то, что в определенном смысле все три введенные нормы эквивалентны: каждая из них оценивается любой из двух других норм с точностью до множителя, зависящего от т. Пример 5.1. Найдем ~х11п 11х112, ~ х11„для вектора х = (0.12, — 0.15, 0.16)т. 124 правых частей.
Удобной для этой цели количественной характеристикой является широко, используемое понятие нормы вектора. Говорят, что в В" задана норма, если каждому вектору х из Я'" сопоставлено вещественное число 1х11, называемое нормой вектора х и обладающее следующими свойствами: 1о) 11х11 ~ О, причем 11х11 = О тогда и только тогда, когда х = О; 2о) 11ах~ = 1ее1 11х11 для любого вектора х и любого числа а; Зо) 11х+ у11 ( 1х1 + 11у~ для любых векторов х и у; последнее неравенство принято называть неравенетвози треуьольника. Заметим, что такими же свойствами обладает обычная геометрическая длина вектора в трехмерном пространстве. Свойство Зо в этом случае следует из правила сложения векторов и из того известного факта, что сумма длин двух сторон треугольника всегда больше длины третьей стороны. Существует множество различных способов введения норм. В вычислительных методах наиболее употребительными являются следующие три нормы: По формулам (5А) определяем !!х!!1 = 0.12 + 0.15 + 0.16 = 0.43, !!х!!г 1/ (О 12г + 0 15г + 0 16г) — 0.25, $х!!„= в<ах ЕО.12, 0.15, 0.161 = 0.16.
2 Скалярное произведение. Напомним, что скалярным произведением вектоРов х = (х<, хг, ..., ха) и У = (У1, Уг, ..., Уа) называетсЯ величина а (х~ У) = х1У1 + хгУг + -. + хтУт = г х<У< (5.7) <=1 Нетрудно установить, что !!х!!г = (х, х)1~г. В случае, когда векторы х, у имеют комплексные компоненты, скалярное произведение понимают так: (х> У) = х<У1 + хгУг + " + хаУа. 3. Абсолютная и относительная погрешности вектора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
