- •Понятие математической модели.
- •Устойчивость.
- •Типы погрешностей.
- •Приближенные числа. Абсолютные и относительные погрешности.
- •Округление.
- •Погрешности арифметических операций над приближенными числами.
- •Погрешность функции.
- •Представление вещественных чисел.
- •Арифметические операции над числами с плавающей точкой.
- •Вычисление машинной точности.
- •Методы отыскания решений нелинейных уравнений.
- •Система линейных алгебраических уравнений.
- •Вычисление lu-разложения (метод Гаусса).
- •Вычисление luр-разложения (метод Гаусса с выбором ведущего элемента).
- •Система линейных алгебраических уравнений.
- •Метод прогонки.
- •Система линейных алгебраических уравнений.
- •Итерационные методы решения систем линейных алгебраических уравнений.
- •Одномерная минимизация.
- •Методы прямого поиска.
- •Оптимальный пассивный поиск.
- •Постановка задачи приближения функций.
- •Полиномиальная интерполяция. Многочлен Лагранжа.
- •Минимизация погрешности оценки интерполяции. Многочлены Чебышева. Постановка задачи минимизации оценки погрешности.
- •Многочлены Чебышева.
- •Постановка задачи приближения функций. В13
- •16 Глобальные способы построения кубических сплайнов.
- •17 Граничные условия для кубических сплайнов
- •Метод наименьших квадратов.
- •Методы численного дифференцирования. Численное дифференцирование.
- •Устойчивость.
- •Адекватность дискретной модели исходной математической задаче;
- •Сходимость численного решения к точному решению;
- •Устойчивость выбранного метода решения.
- •Численное интегрирование. Формулы прямоугольников и трапеций/Формула Симпсона
- •Методы Монте-Карло.
- •Обыкновенные дифференциальные уравнения. Метод Эйлера.
- •Обыкновенные дифференциальные уравнения.
Система линейных алгебраических уравнений.
Рассмотрим систему линейных уравнений с постоянными коэффициентами:
а11х1 + а12х2 + а13х3 + … + а1тхт = b1,
а21х1 + а22х2 + а23х3 + … + а2тхт = b2,
а31х1 + а32х2 + а33х3 + … + а3тхт = b3,
………………………………………….
аm1х1 + аm2х2 + аm3х3 + … + аmтхт = bm .
В матричной форме записи эта система принимает вид Ax = b, где
, , .
Будем предполагать, что матрица А задана и является невырожденной. Известно, что в этом случае решение системы существует, единственно и устойчиво к входным данным, т.е. рассматриваемая задача является корректной.В системе Ах = b из п уравнений с п неизвестными можно было бы пытаться вычислять обратную матрицу А-1 и умножать её на вектор b. Однако, на практике этот подход часто сталкивается с вычислительной неустойчивостью: вещественные числа хранятся в памяти лишь приближённо и ошибки округления могут накапливаться.
Итерационные методы решения систем линейных алгебраических уравнений.
Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций.
Метод простой итерации. Для того чтобы применить метод простой итерации к решению системы линейных алгебраических уравнений
Ах = b (24)
с квадратной невырожденной матрицей А необходимо предварительно преобразовать эту систему к виду
x = Bx + c . (25)
Здесь В - квадратная матрица с элементами bij (i,j = 1, 2, … , т), с - вектор-столбец с элементами сi (i = 1, 2, … , m).Описание метода. Выберем начальное приближение Подставляя его в правую часть системы (25) и вычисляя полученное выражение, находим первое приближение
х(1) = Вх(0) + с.
Подставляя его в правую часть системы (25), получим
х(2) = Вх(1) + с.
Продолжая этот процесс далее, получим последовательность х(0), х(1), … , х(п), … приближений, вычисляемых по формуле
х(к+1) = Вх(к) + с , к = 0, 1, 2 … .
В практике вычислений часто используется критерий окончания
12
Одномерная минимизация.
Пусть f (x)-действительная функция одной переменной, определенная на всей действительной прямой Х. Точка называется точкой глобального минимума функции f на множестве Х , если для всех хХ выполняется неравенство . В этом случае значение называется минимальным значением функции f на X . Функцию f часто называют целевой функцией. Точка называется точкой локального минимума функции f , если существует такая -окрестность этой точки, что для всех х из множества Х , содержащихся в указанной -окрестности, выполняется неравенство . Если же для всех таких х , не совпадающих с , выполняется неравенство , то называется точкой строгого локального минимума.
Существуют различные постановки задачи минимизации. В самой широкой постановке требуется найти все точки локального минимума и отвечающие им значения функции f . В приложениях чаще всего возникает задача вычисления конкретной точки локального или глобального минимума. Иногда представляет интерес лишь минимальное значение целевой функции, независимо от того, в какой именно точке оно достигнуто.
Большинство алгоритмов минимизации осуществляет лишь поиск точки локального минимума функции f . Следовательно, предварительно необходимо определить содержащий точку отрезок [a , b], на котором она является единственной точкой локального минимума. Этот отрезок будем называть отрезком локализации точки . Его можно определить, например,
табулированием функции,
построением графика
из физических соображений
из опыта решения аналогичных задач и т.д.
Для некоторых алгоритмов, например, достаточно иметь не отрезок локализации, а хорошее начальное приближение х(0) к .
П усть f -функция, определенная на отрезке [a , b]. Предположим, что на этом отрезке содержится единственная точка локального минимума функции f , причем функция строго убывает при и строго возрастает при . Такая функция называется унимодальной. Унимодальная функция, вообще говоря, не обязана быть непрерывной.
Например, функция, изображенная на рисунке, унимодальна и имеет две точки разрыва.
Достаточное условие унимодальности функции на отрезке [a , b]: если для всех х, принадлежащих данному отрезку, выполнено условие f ''(x) > 0 , то функция унимодальна на данном отрезке.
Обусловленность задачи минимизации. Пусть - точка строгого локального минимума функции f , вычисляемой с погрешностью . Будем считать, что в некоторой окрестности точки имеют границу абсолютной погрешности, равную ., т.е.
.
Здесь f* - приближенные значения функции.
Вследствие того, что ошибки вычисления с равной вероятностью имеют знак "+" или "-", существует такая малая окрестность точки минимума , для которой, основываясь на сравнении вычисляемых значений f *(x) , нельзя достоверно определить ту точку, в которой действительно достигается минимум функции f . Интервал будем называть интервалом неопределенности точки локального минимума.
Оценим величину радиуса интервала неопределенности в предположении, что функция f дважды непрерывно дифференцируема и выполнено условие В этом случае, с учетом того, что , для значений функции f в точках х, близких к , справедливо приближенное равенство из применения ряда Тейлора
.
Оценим минимальное расстояние, начиная с которого точка перестанет попадать в интервал неопределенности. Имеем:
Следовательно, причем и неравенство выполнено . Таким образом,
.
Любое приближенное значение, попавшее в интервал неопределенности, нельзя отличить от значения точки минимума, используя только вычисляемые значения f* функции f . Поэтому верхняя граница значения неопределенности
. (26)
Если задача хорошо масштабирована, т.е. ( порядка 1), , ,то соотношение (26) можно записать в терминах относительных погрешностей .
Отсюда следует, что если , то . Иными словами, если значение функции вычисляется с т верными значащими цифрами, то приближенное значение точки минимума можно найти примерно с т/2 верными значащими цифрами.
Предположим теперь, что для отыскания точки локального минимума можно использовать вычисляемые каким-либо образом приближенные значения производной функции f. Тогда задача минимизации эквивалентна задаче отыскания корня нелинейного уравнения f '(x) = 0. Эта задача обладает значительно меньшей чувствительностью к ошибкам. В частности справедлива следующая оценка границы абсолютной погрешности:
.