- •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. Обратные и некорректные задачи.
8. Алгоритм исключения Гаусса без перестановки строк. Lu- и ldv-разложения.
См. вопрос 4
LU-разложение – представление матрицы A в виде LU, где L – нижняя треугольная матрица, а U — верхняя треугольная матрица. LU-разложение еще называют LU-факторизацией.
LU-разложение используется для решения систем линейных уравнений и для обращения матриц. Этот метод является одной из разновидностей метода Гаусса.
9. Алгоритм исключения Гаусса при наличии вырожденных главных подматриц. Алгоритм с перестановкой строк или с выбором главного элемента.
1) Выбирают первый слева столбец матрицы, в котором есть хоть одно отличное от нуля значение.
2) Если самое верхнее число в этом столбце есть ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.
3) Все элементы первой строки делят на верхний элемент выбранного столбца.
4) Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.
5) Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.
6) После повторения этой процедуры n − 1 раз получают верхнюю треугольную матрицу
7) Вычитаем из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.
8) Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).
9) Чтобы получить обратную матрицу, нужно применить все операции в том же порядке к единичной матрице.
Для решения следующей системы уравнений:
Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:
Проведём следующие действия:
-
К строке 2 добавим: −4 × Строку 1.
-
К строке 3 добавим: −9 × Строку 1.
Получим:
-
К строке 3 добавим: −3 × Строку 2.
-
Строку 2 делим на −2
-
К строке 1 добавим: −1 × Строку 3.
-
К строке 2 добавим: −3/2 × Строку 3.
-
К строке 1 добавим: −1 × Строку 2.
В правом столбце получаем решение:
.
10. Свойства и определения матричных и векторных норм. Теорема Коши – Шварца. Число обусловленности системы линейных уравнений. Геометрический смысл числа обусловленности. Матричная норма
Матричной нормой называется функция, отображающая матричное пространство в действительные числа.
Матричная норма должна удовлетворять условиям:
1)
2)
3)
4)
Примеры норм
Вторая норма:
Матричную норму можно получить исходя из векторных норм.
Матричная норма, индуцируемая векторной нормой, записывается:
Значение x, при котором обеспечивается максимальное значение отношения характеризует направление, в котором имеет место наибольшее растяжение вектора x.
Матрицу A можно считать оператором, который преобразует вектор x в новый вектор.
Определенная таким способом функция, удовлетворяет всем требованиям матричных норм.
Векторная норма ,
– матричная норма матрицы A
– векторная норма вектора x
К матричным нормам, индуцируемым векторной нормой относятся векторные нормы:
– сумма по столбцам
– сумма по строкам
Для Евклидовой нормы справедливо неравенство Коши-Шварца:
Доказательство
Рассмотрим сумму двух векторов:
c a b
, ,
Из того, что многочлен представляет собой норму, то его величина больше нуля.
Для того, чтобы отсутствовали действительные корни этого многочлена необходимо выполнение условия: детерминант меньше нуля, т.е. .
Если детерминант имеет действительные корни, то многочлен может принимать либо отрицательные значения, либо ноль, что противоречит требованию, что он является нормой.
Исходя из этого неравенства получим:
– норма.
Числом обусловленности матрицы A или соответствующей этой матрице системе уравнений называют произведение нормы матрицы A на норму обратной матрицы:
Матрица A называется хорошо обусловленной, если коэффициент обусловленности имеет небольшую величину.
Пример хорошо обусловленной матрицы:
Определитель –
Пример плохо обусловленной матрицы: