МУ к лабораторным работам (1238837), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

ниже). Трехслойный метод вычислительно устойчив, не уступает двухслойному методу по скорости сходимости но, в отличие от последнего, не требует оптимизации набора параметров  k . Трехслойный метод Чебышева уступает двухслойномуметоду по затратам памяти ЭВМ.4.9. Метод с оптимальным набором параметровЭтот метод является развитием метода простых итераций, когдапараметр  зависит от номера итерации. Пусть A  A *  0. Бу71дем решать уравнение Ax = f с помощью итерационного методаx p 1  x p   p 1 (Ax p  f ),p = 0, 1, 2, …,(4.18)где x 0 — некоторое начальное приближение.Зафиксируем некоторое натуральное n. Поставим задачувыбрать такой набор итерационных параметров 1 ,  2 , …,  n ,при котором норма погрешности || x  x n || на n-й итерации минимальна. Такими являются следующие параметры: k 1 01 0kk = 1, 2, …, n,,(4.19)где0 2 min   max min max0 , k  cos,1 1 (2 k  1) 2n,(4.20).Здесь  min и  max — соответственно минимальное и максимальное собственные значения.Т еор ем а 6.

Если выбрать  k согласно (4.19) и (4.20), тодля погрешности  n  || x  x n || справедлива оценка n  q n || x 0  x ||,гдеqn 21n1  12n,1 1 .1 Итерационный метод (4.18)–(4.20) иногда называют двухслойным итерационным методом Чебышева. Отметим, что  kсвязано с k-м нулем многочленов Чебышева.Как уже отмечалось выше, при проведении вычислений сограниченным числом значащих цифр двухслойный метод можетоказаться неустойчивым к росту ошибок округления. Для устойчивости метода необходимо упорядочить набор параметров  k .Этой проблемы можно избежать, применяя трехслойный методЧебышева, описанный выше.

В настоящее время двухслойный72метод применяется редко.4.10. Метод минимальных невязокПусть по-прежнему матрица A  A *  0. Обозначим черезr p  Ax p  f(4.21)невязку, получающуюся при подстановке некоторого значения x pв уравнение Ax = f. Итерационный алгоритм запишем в видеx p 1  x p   p 1r p ,p = 0, 1, 2, …,(4.22)где x 0 — некоторое начальное приближение.Методом минимальных невязок называется итерационныйметод (4.22), в котором  p 1 выбирается из условия минимума|| r p 1 || при заданной норме || r p || . Минимум нормы невязки|| r p 1 || достигается, если p 1 ( Ar p , r p )|| Ar p || 2.Метод минимальных невязок (4.22), (4.23) сходится с тойже скоростью, что и метод простой итерации с оптимальнымпараметром.Метод минимальных невязок по своей идее близок к методу сопряженных градиентов и отличается от последнегофункционалом, который минимизируется на каждом шаге итераций.4.11.

Метод скорейшего спускаПусть матрица A  A *  0. Рассмотрим итерационный алгоритм (4.22) из предыдущего раздела:x p 1  x p   p 1r p ,p = 0, 1, 2, …Здесь r p  Ax p  f , x 0 — некоторое начальное приближение.Определим вектор z p  x p  x. Введем норму|| r || A  ( Ar, r ) .73В методе скорейшего спуска  p 1 находится из условия минимума || z p+1 || A при заданном векторе z p .

Оказывается, что k 1 (r p , r p )( Ar p , r p ).Метод скорейшего спуска сходится с такой же скоростью,что и метод простой итерации с оптимальным параметром.4.12. Контрольные вопросы1. Выпишите расчетные формулы для метода Зейделя и методаверхней релаксации.2. Покажите, что для самосопряженной матрицы A число обусловленности( A) |  max ||  min |,где  — собственное значение матрицы A. Покажите, что в этомслучае  ( A 2 )   2 ( A ).3. Как изменится число обусловленности матрицы, если умножить ее на ненулевую константу? Покажите, что для произвольных невырожденных матриц A и B выполняется неравенство( AB)  ( A) (B).4. Дана система 10 x1 x1 x1 x2 1, 10 x2  x3 2,x98 x2 x100 x100 99, a. 10 x99Предложите алгоритм, позволяющий экономно вычислять совокупность решений, отвечающих различным значениям a.У ка з а ние.

Алгоритм разобран в [17].5. Рассмотрим матрицу A размером 30  30, где74A120000000010210200000000       0 0 0 0 0 0 1 20000000.1Оцените (A).Наряду с A рассмотрите матрицу B, являющуюся возмущением A:B  A  Ω,где матрица Ω такая, что  30, 1  2 29 , а остальные ее элементы равны нулю. В этом случае || Ω ||  229.

Как изменилсяопределитель при переходе от матрицы A к матрице B?5. Для системы 10 3 x1x1 x2 x2 b1 , b2 ,ответьте на следующие вопросы:а) каково число обусловленности системы;б) какова допустимая относительная погрешность b призаданном фиксированном векторе b  (b1, b2 ) т , при которой относительная погрешность не превосходит 10 2 ;в) каково наименьшее число , при котором независимо отb и b выполняется оценка|| x |||| x |||| b |||| b ||.4.13.

Порядок выполнения работы1. Численно решите систему уравнений Ax = f размером N  Nметодом простой итерации. Матрица A является треугольной.По диагонали у матрицы A расположены числа, принимающиезначение r, за исключением элемента a11 , который равен еди75нице. На одной диагонали выше главной элементы матрицыпринимают значение  r , остальные элементы равны нулю.Правую часть системы считать нулевой.Попытайтесь применить метод простой итерации с параметром, равным 1, для значений N = 5, 10, 20 и r = 3/2.Как видим, необходимые и достаточные условия сходимостиметода простой итерации выполнены (теорема 3 из п. 4.5 — метод простой итерации). Тем не менее, результат может оказатьсяотличным от ожидаемого.

Подумайте, как это можно объяснить.2. Попытайтесь решить методом сопряженных градиентов систему линейных уравнений с матрицей A и правой частьюb  (1, 103 , 10 6 , 10 9 , 1012 ) т ,A  diag (1, 10 3 , 10 6 , 10 9 , 1012 ).Объясните полученный результат.При решении систем уравнений с плохо обусловленнойматрицей иногда помогает введение масштабирования. Нетрудно догадаться, к какому эквивалентному виду надо привестисистему уравнений в задаче 2, чтобы можно было с успехомприменить метод сопряженных градиентов. Аналогичный переход помогает и при решении системы задачи 3.3.

Методом простых итераций со значением итерационного параметра  = 0,3 и начальным приближением x 0  (1, 1) решитесистему с нулевой правой частью и с матрицей:2 11 2.Определите оптимальное значение  и сравните требуемое для сходимости число итераций с предыдущим. Объясните результат.4. Найдите решение системы 10 3 x  y  5,x  y  6,простым методом Гаусса и с выбором главного элемента.

Вычисления вести с двумя знаками. Объясните результаты.764.14. Некоторые рекомендациипо работе с программойПоясним основную схему работы с программой. Прежде всегонеобходимо задать условие задачи. Определение условия задачиравносильно заданию:1) матрицы;2) вектора (правая часть);3) целого числа — размерности матрицы;4) двух чисел с плавающей точкой — границ спектра;5) параметра.Последние три числа входят в стандартное условие задачи,и их нужно задавать.

Введя условие (с клавиатуры или из заранее созданного файла), рекомендуется выбрать режим вывода наэкран, после чего можно запускать программу на счет с помощью пункта меню «Запуск». По мере необходимости можно записывать введенные с клавиатуры матрицы в файлы или в стек.Работа программы. После начала работы программы на экранебудет демонстрироваться невязка по компонентам, если включен соответствующий режим, а по достижении заданного значения невязки программа выведет на экран полученное решение играфик зависимости нормы невязки от номера итерации.В любой момент можно остановить счет, нажав произвольную клавишу на клавиатуре или на мыши.

Тогда после утвердительного ответа на вопрос, хотите ли Вы остановить программу,выдается вся информация, известная на текущий момент (текущее приближение) и т. д.Имеется возможность ввода матрицы (и параметров) из пяти файлов matrix1.dat, …, matrix5.dat.Формат файлов matrix следующий:Na11 a12  a1N 1 a1Na21 a22  a2 N 1 a2 N..................................................a N1 a N 2  a NN 1 a NNb1b2  bN 1bNY1Y277Здесь N — размерность матрицы; aij — элемент матрицы A;Y1 — нижняя граница спектра; Y2 — верхняя граница спектра; — параметр.Пользователю предоставляется возможность производитьс матрицами следующие действия:1) умножить текущую матрицу на сопряженную ей;2) вычислить матрицу, обратную текущей;3) запомнить текущую матрицу в стеке;4) заменить текущую матрицу извлеченной из стека;5) вычислить спектр текущей матрицы.Редактирование текущей матрицы осуществляется аналогичновводу с клавиатуры, при этом у пользователя не запрашиваетсяразмерность матрицы.В программе предусмотрен стек данных.

Элементом стекаявляется структура, состоящая из матрицы, вектора, значенийграниц спектра и параметра . В стек помещаются все перечисленные выше текущие данные. Емкость стека ограничена толькоразмером свободной памяти.4.15. Библиографическая справкаПрикладная (машинная) линейная алгебра — обширная, бурноразвивающаяся отрасль математики.

Для знакомства с ней рекомендуем книгу [5], в которой существует также обзор работ поданной тематике. Полезно также ознакомиться с работами [17–19], где обсуждаются различные аспекты линейной алгебры.Отдельной темой является работа с матрицами специального вида — так называемыми разреженными матрицами, см.книги [5, 20, 21] и библиографии в них.78Л АБОР АТ ОРН АЯ РАБОТ А 5ЧИСЛЕННОЕ РЕШЕНИЕНЕЛИНЕЙНЫХ УРАВНЕНИЙ5.1.

ВведениеВ этой работе Вы познакомитесь с итерационными методами решения нелинейных уравнений. Предусматривается возможностьна характерных примерах рассмотреть и сравнить различные численные методы решения нелинейных уравнений. Сравнение проводится по числу итераций и затратам времени ЭВМ.В предложенной работе используются следующие методырешения нелинейных уравнений:1) метод простой итерации;2) метод Ньютона;3) метод секущих.Первые два метода можно перенести на системы нелинейныхалгебраических уравнений, а также на уравнения в произвольных метрических пространствах.5.2.

Нелинейные уравнения. Теоретическая справкаНелинейные уравнения и системы уравнений решаются с применением итерационных методов. Итерационные методы (ихназывают также методами последовательных приближений) состоят в том, что решение x* находится как предел последовательных приближений x n при числе итераций n, стремящемся кбесконечности. Обычно задаются числом  > 0 и вычисленияпроводят до тех пор, пока не будет выполнена в норме оценка|| x*  x n ||  .Так как точное решение x* неизвестно, то это условие на практике часто заменяют лишь необходимым, но легко проверяемым79условием|| x n  x n 1 ||  .Выполнение этого «условия сходимости» еще не гарантирует,что итерационный процесс сходится.Текущее значение || x n  x n 1 || на экране монитора привыполнении работы называется термином «погрешность».

Такое название является условным, так как на самом деле погрешностью является || x *  x n || .При решении нелинейных уравнений возникают две задачи: указание областей, в которых находится по одному решению (задача локализации корней), и задача отыскания корней сзаданной точностью (задача уточнения корней). Для локализации корней не существует общих приемов. Можно использовать построение графиков функции, отыскание участков еемонотонности, участков на которых функция меняет знак, идругие частные приемы.5.3.

Характеристики

Список файлов книги