- •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. Обратные и некорректные задачи.
Метод исключения Гаусса без перестановки строк
На этапе нужно выполнить следующие шаги:
В результате мы получим верхнюю треугольную матрицу .
При этом левая треугольная матрица в разложении может быть записана:
Нижняя треугольная матрица с единицами на главной диагонали, называется нижней унитреугольной матрицей.
Аналогично, верхняя треугольная матрица с единицами на главной диагонали, называется верхней унитреугольной матрицей.
С помощью первой элементарной операции, заключающейся в вычитании строк мы привели расширенную матрицу к виду, состоящему из верхней треугольной матрицы и вектора, представляющего правую часть преобразованного уравнения.
Верхний индекс обозначает номер преобразования.
Матрица является нижней треугольной матрицей и решение преобразованной системы может быть получено методом обратной подстановки.
Верхняя треугольная матрица .
При верхний предел суммирования равен нулю.
Матрица с коэффициентами является нижней унитреугольной.
Решение этой системы осуществляется методом прямой подстановки.
После нахождения вектора y находится решение
Эти системы являются эквивалентными, а, значит, их решения совпадают.
Эквивалентность систем следует из того, что преобразование матриц осуществляется с помощью первой элементарной операции: вычитание строк, умноженных на некоторые коэффициенты.
Коэффициенты матрицы L вычисляются по формуле:
Для того, чтобы операция исключения Гаусса без перестановки строк могла быть осуществлена, необходимо, чтобы все коэффициенты отличались от нуля, это необходимо, чтобы могло быть осуществлено деление.
Необходимое условие того, что это не произойдет, заключается в теореме о LU-разложении.
Если матрица A имеет невырожденными все ведущие главные подматрицы , то матрица A единственным образом разлагается в произведение матриц L и U.
Ведущая главная подматрица матрицы – матрица порядка , образованная из элементов матрицы А, стоящих на пересечении первых j и первых i строк.
Этот метод является частным случаем метода подстановок Гаусса.
Определители верхней и нижней треугольной матрицы равен произведению диагональных элементов матрицы:
Пример в MathLab:
for i = 1:n;
for j = 1:n-1;
остановка (система вырождена)
Количество операций:
Рассмотренный метод – метод подстановки по строкам.
Если первые k компонентов вектора b будут равны нулю, то число операций уменьшится до .
Модификацией этого метода является метод прямой подстановки по столбцам.
В методе прямой подстановки по столбцам осуществляется последовательное понижение порядка системы уравнений с помощью разбиения матрицы на блоки.
– сложность алгоритма.
for i = 1:n;
система несовместная
for j = i+1:n
Решение системы с верхней треугольной матрицей производится аналогичными способами вверх.
5. Решение систем линейных уравнений с симметричными и положительно определенными матрицами. Разложение Холесского с внутренним произведением.
Разложе́ние Холе́цкого –
Разложение Холецкого – представление симметричной
положительно-определённой матрицы A в виде A = LLT, где L – нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: A = UTU, где U = LT – верхняя треугольная матрица.
Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.
Существует также обобщение этого разложения на случай комплекснозначных матриц. Если A – положительно-определённая эрмитова матрица, то существует разложение , где L — нижняя треугольная матрица с положительными действительными элементами на диагонали, а — эрмитово-сопряжённая к ней матрица.
Для симметричных или эрмитовых положительно определенных матриц применяется разложение Холецкого:
A = UT U или A = L LT (для симметричных),
A = UH U или A = L LH (для эрмитовых),
где
U - верхняя треугольная матрица;
L - нижняя треугольная матрица.