- •Численные методы
- •Решение трансцендентных и алгебраических уравнений
- •Постановка задачи
- •Метод половинного деления
- •Метод хорд
- •Метод итераций
- •Метод Ньютона
- •Модифицированный метод Ньютона
- •Метод секущих
- •Интегрирование функций Постановка задачи
- •Формула прямоугольников
- •Алгоритм программы метода прямоугольника
- •Формула трапеций
- •Формула Симпсона
- •Квадратурная формула Чебышева
- •Квадратурная формула Гаусса
- •Методы решения слау Постановка задачи
- •Метод Крамера
- •Метод Гаусса
- •Связь метода Гаусса с lu-факторизацией
- •Вычисление определителя
- •Обращение матрицы
- •Алгоритм схемы Халецкого
- •Вычисление невязки решения
- •Итерационные методы
- •Теорема Самарского о сходимости стационарных методов
- •Метод Якоби
- •Алгоритм метода Якоби
- •Возможные ошибки
- •Теорема сходимости метода Якоби
- •Рекомендации
- •Метод Зейделя
- •Интерполяционный многочлен Лагранжа
- •Интерполяционная формула Ньютона.
- •Интерполяционные и экстраполяционные формулы при равноотстоящих значениях аргумента.
- •Формула Ньютона для интерполирования вперед и экстраполирования назад
- •Формула Ньютона для интерполирования назад и экстраполирования вперед
- •Интерполяционные формулы Гаусса.
- •Построение кривой по точкам Общие понятия
- •Метод наименьших квадратов
- •Метод линеаризации данных по методу наименьших квадратов.
- •Интерполирование сплайнами Кусочно-линейное и кусочно-квадратичное интерполирование
- •Простейший подход к сглаживанию
- •Кусочно-кубические сплайны
- •Список литературы
Алгоритм схемы Халецкого
Вводим матрицу Aи векторf.
Обнуляем вспомогательные матрицы BиC.
Задаем первый столбец Bи первую строкуCпо формулам (3.7) и (3.8).
Вычисляем остальные элементы матриц BиC.
Перебор строк (цикл iот 1 доN)
Перебор столбцов (цикл jот 1 доN)
Если , то вычисляемпо формуле (3.7).
Если , положим.
Если , то вычисляемпо формуле (3.8).
Конец перебора строк и столбцов.
Проверяем правильность вычисления матриц BиC. Для этого достаточно вычислить произведениеи сравнить сA.
Определим вектор yпо формуле (3.9).
Вычислим решение xпо формуле (3.10).
Выведем матрицу Aи вектор правой частиf, решениеxи невязкуAx-fна экран.
Вычисление невязки решения
Для проверки правильности решения системы линейных алгебраических уравнений необходимо вычислить невязку решения. Невязка vявляется вектором и вычисляется по формуле
, (3.11)
где - приближенное решение системы уравненийAx=f.
Если решение является точным решением, то невязкаvбудет равна нулевому вектору. При решении задачи на компьютере, точное решение получить практически невозможно из-за ошибок округления. Приближенное решение является приемлемым, если его невязка не будет превосходить заранее заданной погрешностиEps.Обычно погрешностьEpsравна 0.001, но это значение можно изменять в зависимости от поставленной задачи и требуемой точности решения.
Итерационные методы
Итерационные методы основаны на построении итерационной последовательности , сходящейся к искомому решению системы.
Каждый такой метод характеризуется своей итерационной формулой, позволяющей вычислять очередное приближение по ранее найденным.
В простейшем случае при вычислении используется только одно приближение. Такие методы называют одношаговыми или двухслойными. Итерационную формулу для одношаговых методов принято записывать в стандартной канонической форме.
. (3.12)
где - итерационный параметр (>0),- вспомогательная невырожденная матрица.
Метод называется стационарным, если для и.
Стационарные методы - наиболее простые с точки зрения организации вычислительного процесса. Однако нестационарные методы имеют другие преимущества, связанные с выбором идля ускорения сходимости итерационного процесса.
Определение очередного приближения с помощью итерационной процедуры (3.12) требует решения уравнения
, (3.13)
где
.
Такую процедуру приходится выполнять на каждом шаге. Поэтому итерационный метод можно применять при условии, что определение отдельных членов итерационной последовательности требует существенно меньшего объема вычислений, чем прямое решение исходной системы. Это накладывает ограничения на выбор матрицы.
Самый простой случай, когда . Тогда формула (3.13) приобретает вид
. (3.14)
Итерационные методы, со схемой вычислений (3.14), называются явными.
Среди неявных методов () наибольшее распространение получили методы с треугольной матрицей.
Разность между приближенным решением и точным решениемназывается погрешностью.
Погрешность удовлетворяет итерационной формуле:
.
Итерационный процесс сходится , еслипри.
Матрица называется транспонированной матрицей, что записывается, еслидля всех.
Матрица называется симметричной (), еслидля всех.
Матрица называется положительно определенной (), если дляимеем.
Матрица называется матрицей с диагональным преобладанием, если ее элементы удовлетворяют неравенству:
для любого.
Примеры:
, и.
- симметричная матрица, и- несимметричные.
- не положительно определенная, т.к. для имеем.
- положительно определенная, т.к. для получаем.
и - без диагонального преобладания,- с диагональным преобладанием.