- •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. Обратные и некорректные задачи.
6. Разложение Холесского с внешним произведением и с поблочным вычислением матриц.
Теорема
Любая положительно-определенная матрица может быть представлена в виде произведения двух матриц: нижней треугольной матрицы и транспонированной к ней верхней треугольной матрицы.
– нижняя треугольная матрица
– верхняя треугольная матрица
Матрица называется положительно-определенной, если она невырождена, если все ее коэффициенты – действительные числа, и если при любом ненулевом векторе , величина
Положительно-определенная матрица является симметричной, т.е. .
Из того, что матрица является положительно-определенной, т.е. она невырождена, действительная и при любом векторе произведение :
1)
2)
3)
Приравнивая элемента строки получим уравнение:
При
Все действия алгоритма является выполнимыми, если матрица является положительно- определенной матрицей.
Существуют разные модификации метода разложения Халецкова. Мы остановимся на одной: метод Халецкова с внешним произведением.
В этом методе используется блочное представление матриц, а именно матрица записывается в виде:
Размер матрицы на 1 меньше размера матрицы ,
0 – нулевой вектор
1)
2)
4) , размер матрицы на 1 меньше, чем размер матрицы .
По приведенному вычисляются значения первой строки и первого столбца .
До тех пор, пока матрица не станет равной .
Число операций, необходимых для выполнения этого преобразования равно .
Доказательство теоремы Халецкого
-
Нужно доказать, что
, ,
-
Извлечение корня и деление допустимы во всех случаях. Нужно доказать, что – положительно определенная матрица.
Если матрица представлена в блочной форме: , и , – квадратные матрицы, т.е. , , то из того, что матрица – положительно-определенная, следует, что матрицы и – положительно-определенные
.
Этот алгоритм справедлив только для положительно-определенной матрицы.
Помимо двух рассмотренных алгоритмов, существует окаймляющая форма метода Халецкова и метод побочного вычисления.
7. Метод исключения Гаусса и lu-разложение. Понятие эквивалентности систем уравнений, понятие и состав элементарных операций.
См. вопрос 4 или:
Процесс решения системы линейных уравнений
по методу Гаусса состоит из 2х этапов:
Прямой ход
Система (2) приводится к треугольному виду
1. Предполагаем, что . Тогда первое уравнение системы (2) делим на коэффициент , в результате получаем уравнение
Затем из каждого из оставшихся уравнений вычитается первое,
умноженное на соответствующий коэффициент , в результате система преобразуются к виду:
2. В предположении, что , делим второе уравнение на коэффициент и исключаем неизвестное из всех последующих уравнений и т.д.
3. Получаем систему уравнений с треугольной матрицей:
Если матрица A имеет невырожденными все ведущие главные подматрицы , то матрица A единственным образом разлагается в произведение матриц L и U.
Системы называются эквивалентными, если они имеют одно и тоже решение.
Элементарные операции – операции, при которых в результате перестановки система является эквивалентной предыдущей системе.
Элементарные операции:
1) перестановка строк;
2) умножение строки на число, отличное от нуля;
3) сложение строки с другой строкой, умноженной на число.