Основные требования, предъявляемые к вычислительным алгоритмам. Системы линейных алгебраических уравнений. Устойчивость и точность прямых методов. Модификации концепции сопряженных градиентов. Анализ формулы Симпсона для вычисления двойных интегралов.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ РАДИОФИЗИКИ И ЭЛЕКТРОНИКИЛекция 12. Лекция 13. Многошаговые методы 13.1 Явные многошаговые методы АдамсаПрямые методы в отсутствии ошибок округления позволяют получить точное решение системы . Современные вычислительные машины оперируют с конечными десятичными дробями, представленными в форме с плавающей точкой. A и вектора в памяти ЭВМ вносится ошибка округления и реально решается возмущенная система A, - компонент вектора , ? - число, характеризующее относительную погрешность машинной арифметики. Очевидно, что вследствие ошибок округления при реализации на ЭВМ прямого метода это решение не будет точно удовлетворять системе .Рассмотрим влияние возмущений матрицы системы и вектора правой части на точность решения. , где - точное решение, в любой согласованной норме подчиняется неравенству Такое неравенство означает, что норма матрицы возмущений существенно меньше нормы исходной матрицы, т. е. предполагается, что прямой метод решения линейной системы устойчив. Относительная ошибка решения системы прямым методом может достигать величины, определяемой произведением числа обусловленности и суммы относительных возмущений матрицы системы и вектора правой части. Если число обусловленности велико, то даже при малых эквивалентных возмущениях матрицы и вектора правой части погрешность решения линейной системы оказывается значительной.По этой причине g(A) называют коэффициентом роста матрицы Элементы активной части матрицы Ak в методе Гаусса вычисляются по формуле Это достигается процедурой выбора элемента , который называют главным. В этой стратегии в качестве главного элемента при исключении неизвестной xk выбирается элемент по правилу Устойчивость вычислительной схемы метода определяется величиной коэффициента роста элементов матрицыПредположим, что Q - неособенная-матрица, рассматриваемая как апроксимация матрицы Это имеет место тогда, когда матрица Q является нижней треугольной, верхней треугольной, трех-диагональной, произведением конечного числа таких простых матриц и т.п. Матрицу Q называют матрицей расщепления. Запишем метод Якоби в координатной форме для системы общего вида: Нетрудно убедиться, что метод Якоби в координатной форме есть не что иное, как разрешение каждого из уравнений системы относительно одной из компонент вектора. Запишем метод Гаусса-Зейделя в координатной форме для системы общего вида: Координатная форма метода Гаусса-Зейделя отличается от координатной формы метода Якоби лишь тем, что первая сумма в правой части итерационной формулы содержит компоненты вектора решения не на k-й, а на (k 1)-й итерации.Свойство сопряженности означает, что . Это свойство в СГ-алгоритме обеспечивается выбором параметра b. Векторы , построенные по СГ-алгоритму, линейно независимы. Умножим левую и правую части этого равенства слева сначала на Умножим последнее равенство слева на и преобразуем его правую часть, привлекая свойство сопряженности (для ): .вследствие того, что В итоге метод сопряженных градиентов принимает экономичную форму: 1. Вычислить Вычислительные затраты на итерации такой экономичной реализации метода сопряженных градиентов при решении СЛАУ с пятидиагональной матрицей сокращаются на время выполнения операций умножения и сложения: . Изменение ошибки на итерациях метода сопряженных градиентов характеризуется неравенством Ключ к построению более эффективного метода сопряженных градиентов сводится к следующему. Формально переобусловливание системы с привлечением матрицы H осуществляется следующим образом: Получили систему линейных алгебраических уравнений причем ; ; , к которой и применяется метод сопряженных градиентов.Пусть задана система нелинейных уравнений решение которой достигается в точке пространства . Полагая, что решение системы достигается на текущей итерации, относительно поправки получим систему линейных алгебраических уравнений: . Тогда , и итерационное правило Ньютона решения системы нелинейных алгебраических уравнений запишется как Такой вид метода Ньютона неудобен на практике, потому что требует вычисления обратной матрицы, а эта операция достаточно трудоемка. На практике метод Ньютона реализуется в следующем виде: Решается система линейных алгебраических уравнений и вычисляется вектор поправки: , где - матрица Якоби системы;Перечислим недостатки метода Ньютона, на устранение которых направлены различные его модификации: трудность задания начального приближения, от которого метод сходится; Чтобы уменьшить вычислительные затраты на итерации, матрица Якоби в этой модификации остается постоянной на протяжении нескольких шагов. Число шагов m, на которых J постоянна, задается в такой модификации в качестве параметра, либо момент перевычисления матрицы Якоби определяется условием Эти методы позволяют обеспечить сходимость метода Ньютона от выбранного начального приближения .
План
Содержание
Введение
Лекция 1. Введение в теорию численных методов
1.1 Основные требования, предъявляемые к вычислительным алгоритмам
Лекция 2. Системы линейных алгебраических уравнений
Лекция 3. Устойчивость и точность прямых методов
3.1 Устойчивость алгебраических методов
3.2 Точность алгебраических методов
3.3 Устойчивость метода Гаусса
3.4 Устойчивость и точность метода LU-факторизации
Лекция 4. Итерационные методы
4.1 Схема итерационных методов
4.2 Метод простой итерации (Метод Якоби)
4.3 Метод последовательной релаксации
Лекция 5. Модификации метода сопряженных градиентов
5.1 Основные свойства метода сопряженных градиентов
5.2 Экономичная форма метода сопряженных градиентов
5.3 Обобщенный метод сопряженных градиентов
Лекция 6. Численное решение уравнений. Метод итераций
6.1 Теорема о сходимости и точности метода итераций
Лекция 7. Метод ньютона для систем и его модификации
7.1 Метод Ньютона для решения систем нелинейных уравнений
7.2 Модификации метода Ньютона. Краткий обзор
7.3 Дискретный метод Ньютона
Лекция 8. Полиномиальная интерполяция
8.1 Интерполяционная формула Лагранжа
8.2 Интерполяционная формула Ньютона
Лекция 9. Сплайн-интерполяция
9.1 Ограничения многочленной интерполяции
Лекция 10. Методы численного интегрирования
10.1 Формула Симпсона для вычисления двойных интегралов
10.2 Вычисление многомерных интегралов методом Монте-Карло
Лекция 11. Численное решение систем обыкновенных дифференциальных уравнений
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
