Аппроксимация нелинейных характеристик. Интерполяция

Численные методы решения задач

Радиофизики и электроники

(Учебное пособие)

Воронеж 2009

Утверждено Научно-методическим советом физического факультета 4 мая 2008 года, протокол № 5

Учебное пособие подготовлено на кафедре электроники физического

факультета Воронежского Госуниверситета.

Рассматриваются методы решения задач, связанных с автоматизированным анализом электронных схем. Излагаются основные понятия теории графов. Приводится матрично-топологическая формулировка законов Кирхгофа. Описываются наиболее известные матрично-топологические методы: метод узловых потенциалов, метод контурных токов, метод дискретных моделей, гибридный метод, метод переменных состояний.

Рекомендуется для магистров и специалистов старших курсов д/о и в/о. Для специальности 010801 (013800)− «Радиофизика и электроника»

Содержание

1. Аппроксимация нелинейных характеристик. Интерполяция. 6

1.1. Полиномы Ньютона и Лагранжа 6

1.2. Сплайн-интерполяция 8

1.3. Метод наименьших квадратов 9

2. Системы алгебраических уравнений 28

2.1. Cистемы линейных уравнений. Метод Гаусса. 28

2.2. Разреженные системы уравнений. LU-факторизация. 36

2.3. Решение нелинейных уравнений 37

2.4. Решение систем нелинейных уравнений 40

2.5. Дифференциальные уравнения. 44

2. Методы поиска экстремума. Оптимизация. 28

2.1. Методы поиска экстремума. 36

2.2. Пассивный поиск 28

2.3. Последовательный поиск 36

2.4. Многомерная оптимизация 37

Список литературы 47

Аппроксимация нелинейных характеристик. Интерполяция.

1.1. Полиномы Ньютона и Лагранжа.

При решении многих задач возникает необходимость в замене функции f, о которой имеется неполная информация или форма которой слишком сложна, более простой и удобной функцией F, близкой в том или ином смысле к f, дающей её приближённое представление. Для аппроксимации (приближения) используются функции F, принадлежащие определённому классу, например, алгебраические полиномы заданной степени. Существует много разных вариантов задачи о приближении функции, зависящих от того, какие функции f аппроксимируются, какие функции F используются для аппроксимации, как понимается близость функций f и F и т.д.

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

Интерполирование функций используется для замены сложно вычисляемой функции другой, вычисляемой проще; для приближённого восстановления функции по её значениям в отдельных точках; для численного дифференцирования и интегрирования функций; для численного решения нелинейных и дифференциальных уравнений и т.д.

Простейшая задача интерполирования заключается в следующем. Для некоторой функции на отрезке [a,b] заданы n+1 значений в точках , которые называются узлами интерполяции. При этом . Требуется построить интерполирующую функцию F(x), принимающую в узлах интерполяции те же значения, что и f(x):

F(x₀) = f(x₀), F(x₁) = f(x₁), …, F(x_n) = f(x_n)

Геометрически это означает нахождение кривой определённого типа, проходящей через заданную систему точек (x_i, y_i), i = 0,1,…,n.

Если значения аргумента выходят за область [a,b], то говорят об экстраполировании – продолжении функции за область её определения.

Наиболее часто функция F(x) строится в виде алгебраического полинома . Существует несколько представлений алгебраических интерполяционных полиномов.

Один из методов интерполирования функций, которая принимает в точках значения - это построение полинома Лагранжа, который имеет следующий вид:

Степень интерполяционного полинома, проходящего через n+1 узлов интерполяции, равна n.

Из вида полинома Лагранжа следует, что добавление новой узловой точки приводит к изменению всех членов полинома. В этом состоит неудобство формулы Лагранжа. Зато метод Лагранжа содержит минимальное количество арифметических действий.

Для построения полиномов Лагранжа возрастающих степеней может быть применена следующая итерационная схема (схема Эйткена).

Полиномы, проходящие через две точки (x_i, y_i), (x_j, y_j) (i=0,1,…,n-1; j=i+1,…,n), могут быть представлены таким образом:

Полиномы, проходящие через три точки (x_i, y_i), (x_j, y_j), (x_k, y_k)

(i=0,…,n-2; j=i+1,…,n-1; k=j+1,…,n), могут быть выражены через полиномы L_ij и L_jk:

Полиномы для четырёх точек (x_i, y_i), (x_j, y_j), (x_k, y_k), (x_l, y_l) строятся из полиномов L_ijk и L_jkl:

Процесс продолжается до тех пор, пока не будет получен полином, проходящий через n заданных точек.

Алгоритм вычисления значения полинома Лагранжа в точке XX, реализующий схему Эйткена, может быть записан с помощью оператора:

for (int i=0;i<N;i++)//Здесь объявлена переменная i

F[i]=y[i];

for (int i=0;i<=N-2;i++)Здесь не нужно слово int, программа

его воспримет как ошибку – повторное объявление переменной,

переменная i уже была объявлена

for (int j=i+1;j<=N-1;j++)

{

F[j]=((arg-x[i])*F[j]-(arg-x[j])*F[i])/(x[j]-x[i]);

}

return F[N-1];

где массив F – это промежуточные значения полинома Лагранжа. Первоначально следует положить F[I] равными y_i. После выполнения циклов F[N] – это значение полинома Лагранжа степени N в точке XX.

Другой формой представления интерполяционного полинома являются формулы Ньютона. Пусть - равноотстоящие узлы интерполяции; i=0,1,…,n; - шаг интерполяции.

1-я интерполяционная формула Ньютона, которая используется для интерполирования «вперёд», имеет вид:

называется (конечными) разностями i-го порядка. Они определяются так:

,

,

,

- нормированный аргумент.

При интерполяционная формула Ньютона превращается в ряд Тейлора.

2-я интерполяционная формула Ньютона используется для интерполирования «назад»:

или

;

В последней записи вместо разностей (называемых разностями «вперёд») употребляются разности «назад» :

,

, …

В случае неравноотстоящих узлов рассматриваются т.н. разделённые разности

,

, …,

При этом интерполяционный многочлен в форме Ньютона имеет вид

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

При n=1 получаем формулу линейного интерполирования:

При n=2 будем иметь формулу параболического интерполирования:

.

При интерполировании функций алгебраические полиномы высокой степени применяются редко из-за значительных вычислительных затрат и больших погрешностей при вычислении значений.

На практике чаще всего используют кусочно-линейное или кусочно-параболическое интерполирование.

При кусочно-линейном интерполировании функция f(x) на интервале (i=0,1,…,n-1) аппроксимируется отрезком прямой

Алгоритм вычисления, реализующий кусочно-линейное интерполирование, может быть записан с помощью оператора:

for (int i=0;i<N-1;i++)

{

if ((arg>=Fx[i]) && (arg<=Fx[i+1]))

{

res=Fy[i]+(Fy[i+1]-Fy[i])*(arg-Fx[i])/(Fx[i+1]-Fx[i]);

break;

}

}

return res;

С помощью первого цикла ищем, где находится искомая точка.

При кусочно-параболическом интерполировании полином строится по 3-м узловым точкам, ближайшим к заданному значению аргумента.

Алгоритм вычисления, реализующий кусочно-параболическое интерполирование, может быть записан с помощью оператора:

for (int i=0;i<N-1;i++)

{

y0=Fy[i-1]; При i=0 элемент [i-1] не существует!

y1=Fy[i];

y2=Fy[i+1];

x0=Fx[i-1]; То же самое

x1=Fx[i];

x2=Fx[i+1];

res=y0+(y1-y0)*(arg-x0)/(x1-x0)+(1/(x2-x0))*(arg-x0)*(arg-x1)*(((y2-y1)/(x2-x1))-((y1-y0)/(x1-x0)));

break;

}

}

return res;

}

Применение интерполирования не всегда целесообразно. При обработке экспериментальных данных желательно производить сглаживание функции. Аппроксимация экспериментальных зависимостей по методу наименьших квадратов исходит из требования минимизации среднеквадратичной ошибки

.

Коэффициенты аппроксимирующего полинома находятся из решения системы m+1 линейных уравнений, т.н. «нормальных» уравнений , k=0,1,…,m

Кроме алгебраических полиномов для аппроксимации функций широко используются тригонометрические полиномы

(см. «численный гармонический анализ»).

Эффективным аппаратом приближения функции являются сплайны. Для сплайна требуется совпадение его значений и производных в узловых точках с интерполируемой функцией f(x) и её производными до некоторого порядка. Однако построение сплайнов в ряде случаев требует значительных вычислительных затрат.

Поиск по сайту: