- •1. Источники и виды погрешностей. Абсолютная и относительная погрешности. Вычислительная погрешность и погрешность функции.
- •3. Решение систем линейных алгебраических уравнений. Правило Крамера и обратная матрица. Вычислительная сложность.
- •4. Решение систем линейных уравнений. Метод исключения Гаусса с верхней и нижней треугольной матрицами. Методы прямой и обратной подстановки. Решение линейных систем алгебраических уравнений
- •Метод исключения Гаусса без перестановки строк
- •5. Решение систем линейных уравнений с симметричными и положительно определенными матрицами. Разложение Холесского с внутренним произведением.
- •6. Разложение Холесского с внешним произведением и с поблочным вычислением матриц.
- •Доказательство теоремы Халецкого
- •7. Метод исключения Гаусса и lu-разложение. Понятие эквивалентности систем уравнений, понятие и состав элементарных операций.
- •8. Алгоритм исключения Гаусса без перестановки строк. Lu- и ldv-разложения.
- •9. Алгоритм исключения Гаусса при наличии вырожденных главных подматриц. Алгоритм с перестановкой строк или с выбором главного элемента.
- •10. Свойства и определения матричных и векторных норм. Теорема Коши – Шварца. Число обусловленности системы линейных уравнений. Геометрический смысл числа обусловленности. Матричная норма
- •Геометрический смысл плохо обусловленных и хорошо обусловленных матриц
- •11. Задачи приближения и интерполяции функций и эмпирических данных.
- •13. Формулы численного дифференцирования интерполяционным методом.
- •14. Формулы численного дифференцирования методом неопределенных коэффициентов.
- •15. Наиболее распространенные формулы численного дифференцирования.
- •16. Задачи и методы численного интегрирования. Квадратурные формулы.
- •Элементарные квадратурные формулы, полученные методом интерполяции
- •17. Численное интегрирование интерполяционными методами.
- •18. Численное интегрирование методом неопределенных коэффициентов.
- •Частные случаи
- •19. Квадратурные формулы Ньютона – Котеса.
- •20. Формулы прямоугольника, трапеций и Симпсона.
- •21. Ортогональные и ортонормальные системы функций и многочленов. Скалярное произведение. Ортогонализация произвольной системы линейно независимых функций. Формула Грама – Шмидта.
- •22. Квадратурные формулы Гаусса. Наиболее распространенные формулы.
- •23. Интегрирование быстро осциллирующих функций. Интегрирование функций на больших интервалах изменения аргумента.
- •24. Тригонометрическая интерполяция и дискретное преобразование Фурье.
- •25. Быстрое преобразование Фурье.
- •26. Задача наименьших квадратов. Прямой метод решения.
- •27. Задача наименьших квадратов. Решение методом qr-разложения.
- •28. Алгоритм qr-разложения. Ортогональные матрицы и матрицы плоского вращения.
- •29. Задача численного решения обыкновенных дифференциальных уравнений. Задача Коши и граничные задачи.
- •30. Решение задачи Коши с помощью формулы Тейлора.
- •31. Методы Рунге – Кутта. Формулы Эйлера и Адамса.
- •32.Конечно-разностные методы решения задачи Коши.
- •33. Явные формулы Адамса.
- •34. Решение задачи Коши методом неопределенных коэффициентов.
- •35. Решение систем обыкновенных дифференциальных уравнений методом Эйлера.
- •36. Определение градиента функции нескольких переменных.
- •Метод градиента
- •37. Матрица Якоби системы функций нескольких переменных.
- •38. Решение нелинейных уравнений методом простой итерации.
- •39. Решение нелинейных уравнений методом Ньютона.
- •46. Необходимые и достаточные условия минимума и максимума функции многих переменных. Необходимые и достаточные условия экстремума функции нескольких (двух) переменных
- •47. Форма функции многих переменных в окрестности точки седла.
- •48. Градиентный метод минимизации функции многих переменных.
- •49. Минимизация функции многих переменных методом Ньютона.
- •Применительно к задачам оптимизации
- •50. Формула и множители Лагранжа в задаче оптимизации
- •Описание метода
- •51. Производная по направлению и возможное направление спуска.
- •52. Обратные и некорректные задачи.
26. Задача наименьших квадратов. Прямой метод решения.
Задача наименьших квадратов, возникающая при научных и инженерных расчетах, может рассматриваться, как задача восстановления зависимости по эмпирическим данным.
Эмпирические данные представляют собой значения неизвестной функции, полученные в результате эксперимента на сетке узлов, в общем случае, неравномерной.
Узлы сетки могут представлять собой моменты времени или пространственные координаты линейной электрической или механической системы.
Координаты узлов и значения функции в этих узлах объединяются в набор точек , где – координаты узлов, – значения функции.
Задача заключается в определении коэффициентов аппроксимирующей функции, которая должна приближать наблюдаемые данные с возможно большей точностью.
Пример: . Такая функция часто используется при отслеживании дрейфа временных рядов в экономике.
В общем случае такая функция может не обеспечить требуемую точность восстановления зависимости. Поэтому в качестве аппроксимирующих функций используются общие многочлены по системе линейно-независимых функций:
Система независимых функций, которая называется системой, может быть представлена в виде степенных функций, тригонометрических функций и др.
В случае степенных функций .
Число базисных функций и размерность пространства базисных функций, как правило, меняет число наблюдаемых данных.
В идеале, желательно, что бы ошибки в узлах сетки имели минимальную величину: .
Если потребовать, чтобы ошибки в узлах сетки были равны нулю, то коэффициенты обобщенного многочлена должны удовлетворять матричному уравнению:
Решения этой системы возможно только при условии, если , и определитель матрицы отличен от нуля: , в противном случае решение этой системы оказывается невозможным. Однако, можно подобрать такие значения коэффициентов многочлена, чтобы полученный многочлен приближал наблюдаемые данные к значениям функции.
Точность восстановления зависимости, представленной вектором невязок можно представить некоторой нормой, которая характеризует среднее значение ошибок по всем узлам.
В качестве нормы можно использовать выражение:
Евклидова норма: или квадрат этой нормы: .
Задача наименьших квадратов возникает из задачи минимизации квадрата евклидовой нормы
Прямой подход к решению задачи минимизации квадрата евклидовой нормы сводится к нахождению коэффициентов, при которых градиент вектора нормы невязки равен нулю.
Градиент функции обозначается оператором Набла.
Градиент функции – вектор первых частных производных функции по компонентам вектора.
Получим систему линейных алгебраических уравнений:
Решение этой системы сводится к нахождению обратной матрицы:
При большой размерности пространства базисных функций, нахождение обратной матрицы является достаточно трудоемкой задачей.
Чтобы преодолеть эту проблему, численные методы решения задачи наименьших квадратов основываются на разложении матриц исходной системы.
Одним из эффективных методов решения задачи является метод QR-разложения.
По этому методу исходная матрица системы уравнений разлагается в произведение матриц: .
Матрица A считается квадратной, если квадратными являются матрицы Q и R.
Матрица Q – ортогональная матрица, а матрица R – верхняя треугольная матрица.
Матрица называется ортогональной, если:
Разложение матрицы A в произведение ортогональной и верхней треугольной матриц позволяет решить алгебраическую систему уравнений в два этапа.
1)
получим систему:
решение системы:
2)
эту систему можно решить методом обратной подстановки.