Формат выходных данных. Формат входных данных

Формат входных данных

Формат входного файла:

m	– метод (в порядке их перечисления);
n	– размерность СНУ;
x^0	– начальное приближение;
ε	– требуемая погрешность решения;
f1 f2 … fn	– система функций.

x^0 x^1 … x^k	– последовательные приближения решения СНУ;
ε^*	– вектор невязки f(x^k);
||ε^*||	– норма вектора невязки.

2.5. Практическая работа №5 «Интерполирование и численное дифференцирование функций»

Обязательных методов
Баллов за обязательные методы
Дополнительных методов
Баллов за дополнительные методы
Количество вариантов

Приближение функций – одна из наиболее востребованных областей численных методов. Под приближением понимается замена на интервале [а, b] исходной функции f (x) некоторой другой функцией P(x), близкой (по некоторому критерию) к исходной функции. В общем случае, P(x) является полиномом вида

(2.5.1)

где c_i – некоторые действительные константы, а φ_i(x) – система действительных линейно-независимых функций. Т.е. любая функция этой системы не может быть представлена в виде линейной комбинации других. Например,

φ_i(x) = sin ⁱ (x).

Задача состоит в том, чтобы, выбрав систему функций, найти такие коэффициенты c_i, при которых отклонение полинома P(x) от исходной функции удовлетворяло бы выдвигаемым критериям. Исходными данными являются узлы x_i, принадлежащие отрезку [а, b] и значения функции в этих узлах y_i = f (x_i), i = 0, 1, …, m. При этом полином P(x) называют приближающим или аппроксимирующим (от англ. approximate – приблизительный):

f (x) = P(x) + R(x), (2.5.2)

где R(x) – т.н. остаточный член.

В данной практической работе мы будем рассматривать такие полиномы, у которых m = n.

Например, аппроксимирующий полином можно построить, воспользовавшись методом наименьших квадратов (МНК). При этом φ_i(x) может быть системой любых линейно-независимых функций, а коэффициенты c_i ищутся из условия минимального СКО полученного полинома от исходной функции:

(2.5.3)

Картина при этом получается примерно следующая (рис. 2.5.1):

Рис. 2.5.1 – Аппроксимация МНК

Если требуется построить такой полином, чтобы он проходил через все точки (x_i, y_i), то его называют интерполирующим (от англ. interpolate). Здесь приставка «inter-» имеет смысл «между». Т.е. нас интересует поведение полинома только между точками (x_i, y_i), т.е. между границами отрезка [а, b]. А критерий близости интерполирующего полинома к исходной функции выглядит как

y_i = P(x_i). (2.5.4)

При этом обычно x₀ = a, x_n = b. Для того же набора точек, что и на рисунке выше, получим следующее:

Рис. 2.5.2 – Интерполяция методом Ньютона или Лагранжа

На рисунке изображены полиномы Ньютона и Лагранжа (в сущности, это разные формы одного и того же полинома степени n), которые мы будем изучать в ходе данной практической работы. Как видно, их недостатком является осцилляция при большом количестве точек. Поэтому их область применения лучше ограничивать теми случаями, когда точек немного. В противном случае нужно пользоваться другими интерполирующими и аппроксимирующими полиномами.

Если же нас интересуют значения полинома P(x) за пределами отрезка [а, b], то такой полином называется экстраполирующим (от англ. extrapolate, где приставка «extra-» имеет смысл «сверх», «за пределами»).

Аппроксимация функций необходима в двух случаях.

Во-первых, если исходная функция неизвестна. Т.е. имеется только некоторая сетка {x_i} и значения функции в узлах сетки {y_i}. В этом случае говорят, что функция задана таблично. Такая ситуация может складываться в любом эксперименте – известно значение искомой характеристики y_i только в некоторых точках x_i в пространстве ее аргументов R^Z, но необходимо иметь возможность найти значения этой характеристики во всех точках некоторого подпространства X^Z Ì R^Z. Например, зная давления в некоторых точках трубы с газом, можно выдать прогноз давления по всей трубе. Это поможет найти области падения давления (т.е. нарушения герметичности трубы) или, наоборот, области повышенного давления (что может привести к прорыву трубы в будущем) и оперативно отреагировать на внештатную ситуацию. Или, зная несколько координат некоторого космического тела, движущегося в пространстве, можно построить достаточно гладкий интерполирующий полином, который ответит на вопрос, как выглядела траектория тела в те моменты, когда мы тела не наблюдали (например, оно было закрыто другими космическими телами или находилось за горизонтом, т.е. было невидимо из-за вращения Земли). Если использовать экстраполирующий полином, то можно узнать, как вела себя траектория тела до начала наблюдений, и как она будет вести себя в будущем.

Во-вторых, даже если аналитический вид функции известен, она может иметь очень сложный вид. Существуют различные задачи в физике, математике и пр. науках, где вычисление некоторых функций в одной точке пространства аргументов может занимать от нескольких секунд до часов, дней и т.д. В этом случае, если время ограничено, вычисляют значение функции только в нескольких узлах (получая табличную функцию) и проводят аппроксимацию или интерполяцию.

Сетка {x_i} при i = 0, 1, …, n имеет n+1 узел. Она может быть равномерной или неравномерной. Если сетка равномерная (т.е. расстояние между ее соседними узлами одинаковое), то все узлы задавать не обязательно. Достаточно знать начальный узел x₀ и шаг сетки h:

x_i = x₀ + ih, i = 0, 1, …, n. (2.5.5)

Если заданы только границы отрезка (точки a и b, или x₀ и x_n), то из (2.5.5) следует, что x_n = x₀ + nh, т.е. шаг можно найти по формуле

(2.5.6)

Все вышесказанное можно отнести также и к задачам численного дифференцирования (заметьте, что, говоря об аппроксимации и упомянутых ее разновидностях, мы не употребляем слово «численная», т.к. это в принципе чисто численные методы). Только в этом случае нас интересует не сама функция, а некоторая ее производная. Поэтому будем заменять производную функции (см. 2.5.2) производной аппроксимирующего полинома:

f ^(k)(x) = (P(x) + R(x))^(k) = P^(k)(x) + R^(k)(x). (2.5.7)

В данной практической работе мы будем находить первую и вторую производные полинома P(x). При этом

(2.5.8)

Дата добавления: 2014-11-20