Элементы теории погрешностей. Интерполяция и аппроксимация функций

Размещено на http://www.allbest.ru/

1. Элементы теории погрешностей

1.1 Определение абсолютной и относительной погрешности численного результата

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

а = А - а.

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

= А - а.

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

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

= А - а а.

Относительной погрешностью приближенного числа а называется отношение абсолютной погрешности этого числа к модулю соответствующего точного числа А (А0) т.е.

.

Так же как и для абсолютной погрешности вводят понятие предельной относительной погрешности. Под предельной относительной погрешностью а понимают всякое число, не меньшее относительной погрешности этого числа. В качестве предельной относительной погрешности числа, а можно принять число

.

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

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

(a b) = a + b.

При умножении или делении чисел друг на друга их относительные погрешности складываются.

 ;

При возведении в степень приближенного числа его относительная погрешность умножается на показатель степени.

Погрешность разности: предельная абсолютная погрешность разности (u = x1 - x2) равна сумме предельных абсолютных погрешностей уменьшаемого и вычитаемого:

u = x1 + x2

Отсюда предельная относительная погрешность разности

где А - точное значение абсолютной величины разности чисел х1 и х2.

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

1 + 2 + ... + n .

Поэтому при вычислении произведения нескольких приближенных чисел применяют следующие правила:

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

- в результате умножения сохраняют столько значащих цифр, сколько верных цифр имеется в наименее точном из сомножителей.

Погрешность частного: относительная погрешность частного не превышает суммы относительных погрешностей делимого и делителя.

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

Пусть задана дифференцируемая функция u=(x1,x2, ... , xn) и пусть xi - абсолютные погрешности аргументов функции.

Тогда предельная абсолютная погрешность функции может быть вычислена по формуле:

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

2. Решение уравнений с одной неизвестной

2.1 Отделение корней уравнения и отделение корней алгебраического уравнения

Всякое уравнение с одним неизвестным можно представить в виде

(x) = g(x),

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

f(x) = 0.

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

Алгебраическое уравнение может быть приведено к виду:

.

Процесс нахождения приближенных значений корней уравнения разбивается на два этапа:

1) отделение корней;

2) уточнение корней до заданной точности.

Корень уравнения f(x) = 0 считается отделенным на отрезке [a, b], если на этом отрезке уравнение f(x) = 0 не имеет других корней.

Отделить корни - это значит разбить всю область допустимых значений на отрезки, в каждом из которых содержится один корень.

Графический метод отделения корней - в этом случае поступают также, как и при графическом методе решения уравнений.

Если кривая касается оси абсцисс, то в этой точке уравнение имеет двукратный корень (например, уравнение x3 - 3x + 2 = 0 имеет три корня: x1 = -2 ; x2 = x3 = 1). Если же уравнение имеет трехкратный действительный корень, то в месте касания с осью х кривая y = f(x) имеет точку перегиба (например, уравнение x3 - 3x2 + 3x - 1 = 0 имеет корень x1 = x2 = x3 = 1).

Аналитический метод отделения корней. Для этого используют некоторые свойства функций.

Теорема 1. Если функция f(x) непрерывна на отрезке [a,b] и принимает на концах этого отрезка значения разных знаков, то внутри отрезка [a,b] существует по крайней мере один корень уравнения f(x) = 0.

Теорема 2. Если функция f(x) непрерывна и монотонна на отрезке [a,b] и принимает на концах отрезка значения разных знаков, то внутри отрезка [a,b] содержится корень уравнения f(x) = 0, и этот корень единственный.

Теорема 3. Если функция f(x) непрерывна на отрезке [a,b] и принимает на концах этого отрезка значения разных знаков, а производная f '(x) сохраняет постоянный знак внутри отрезка, то внутри отрезка [a,b] существует корень уравнения f(x) = 0 и притом единственный.

Порядок действий для отделения корней аналитическим методом:

1) Найти f '(x) - первую производную.

2) Составить таблицу знаков функции f(x), полагая х равным:

а) критическим значениям (корням) производной или ближайшим к ним;

б) граничным значениям (исходя из области допустимых значений неизвестного).

2.2 Понятие кратного корня

Если кривая касается оси абсцисс, то в этой точке уравнение имеет двукратный корень (например, уравнение x3 - 3x + 2 = 0 имеет три корня: x1 = -2 ; x2 = x3 = 1).

Если же уравнение имеет трехкратный действительный корень, то в месте касания с осью х кривая y = f(x) имеет точку перегиба (например, уравнение x3 - 3x2 + 3x - 1 = 0 имеет корень x1 = x2 = x3 = 1).

2.3 Методы уточнения корней простой итерации

Сущность этого метода заключается в следующем. Пусть дано уравнение f(x) = 0, где f(x) - непрерывная функция, и требуется определить ее вещественные корни. Для этого заменяют исходное уравнение равносильным:

x = (x).

Выбрав приближенное значение корня x0 подставляют его в правую часть этого уравнения.

Тогда получают:

x1 = (x0).

После этого процесс продолжают:

x2 = (x1) … xn = (xn-1).

Если эта последовательность - сходящаяся, т.е. существует предел , то, переходя к пределу в выражении xn = (xn-1) и предполагая функцию (x) непрерывной, можно найти:

Или

= ().

Таким образом, предел является корнем уравнения и может быть вычислен по приведенной формуле с любой степенью точности.

На приведенных рисунках процесс итерации сходится (кривая y = (x) в окрестности корня - пологая, т.е. '(x) < 1).

(x)=f(x)+x,

где :

если f '(x)>0, то -1/r<<0; если f '(x)<0, то -1/r>>0, где r=max(| f '(a)|, |f '(b)|).

Однако если рассмотреть случай, где '(x) > 1, то процесс итерации может быть расходящимся.

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

2.4 Метод Ньютона

Пусть корень уравнения f(x) = 0 отделен на отрезке [a, b], причем f '(x) и f "(x) непрерывны и сохраняют определенные знаки при a x b. Найдя какое-нибудь n-е приближение корня xn (a xn b), можно уточнить его по методу Ньютона следующим образом. Положим = xn + hn, где hn считают малой величиной. Отсюда, применяя формулу Тейлора, получим

0 = f(xn + hn) f(xn) + hn f '(xn) .

Следовательно,

Отсюда можно найти следующее (по порядку) приближение корня:



, (n = 0, 1, 2, …)

Как видно из этого рисунка правильный выбор начального приближения обеспечивает удачу в поиске корня. Общее правило - "хорошим" начальным приближением является то, для которого выполняется неравенство:

f(x0) f "(x0) > 0.

Из общей формулы метода вытекает, что чем больше численное значение первой производной в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить n+1 приближение. Поэтому метод Ньютона удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение первой производной близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным.

2.5 Метод хорд

Пусть для определенности f(a) < 0 и f(b) > 0. Тогда, вместо того, чтобы делить отрезок [a, b] пополам, более естественно разделить его в соотношении f(a)/f(b) . Это дает приближенное значение корня x1 = a + h .

Для вычисления значения h можно составить пропорцию (см. рисунок)

Откуда

Далее, применяя этот прием к тому из отрезков [a, x] или [b, x], на концах которого функция f(x) имеет противоположные знаки, получим второе приближение корня и т.д.

Геометрически способ пропорциональных частей эквивалентен замене кривой y = f(x) хордой, проходящей через точки A [a, f(a)] и B [b, f(b)]. Отсюда можно получить еще одну формулу этого метода. Из подобия треугольников вытекает, что

.

Отсюда

.

2.6 Достаточное условие сходимости метода простой итерации

Пусть функция (x) определена и дифференцируема на отрезке [a, b], причем все ее значения (x) [a, b].

Тогда, если выполняется условие

'(x) < 1

при a < x < b, то:

1) процесс итерации xn = (xn-1) (n=1,2,…) сходится независимо от начального значения x0 [a, b];

2) предельное значение является единственным корнем уравнения x = (x) на отрезке [a, b].

Если это условие выполняется не на всем интервале, то метод может как сходиться, так и расходиться.

Вывод условия сходимости:

Так как = () и xn = (xn-1), то можно записать

По теореме о среднем (она утверждает, что если производная функции f(x) непрерывна на некотором интервале [a, b], то тангенс угла наклона хорды, проведенной между точками a и b (т.е. {f(b)-f(a)/(b-a)} равен производной функции в некоторой промежуточной точке, лежащей между a и b) частное в последнем выражении будет равно '(C), где С - некоторая промежуточная точка в интервале поиска корня.

Следовательно

xn - = ' (C) (xn-1 - )

Если ввести обозначение M = max ' (x) для всего интервала поиска, то предыдущее равенство может быть переписано в виде:

xn - M xn-1 -

Аналогично

xn-1 - M xn-2 -

Тогда для xn - будет справедливо неравенство:

xn - M 2 xn-2 -

и т.д. Продолжая эти выкладки дальше, в результате получаем

xn - M n x0 -

где n - натуральное число.

Чтобы метод сходился, необходимо выполнение неравенства:

xn - < M n x0 -

Отсюда следует, что M = max ' (x) должно быть меньше единицы.

В свою очередь, для всех остальных значений ' (x) меньших М, можно записать:

' (x) < 1

2.7 Оценка погрешности n-приближения

Метод хорд:

|x*- xn | (M1-m1)|xn - xn-1|/ m1,

где M1,m1-наибольшее и наименьшее значение |f'(x)| на [a, b].

Метод Ньютона:

|x*- xn | M2(xn - xn-1) 2/2 m1,

где M2-наибольшее значение |f''(x)|, m1- наименьшее значение |f'(x)| на [a, b].

Метод итераций: Пусть - точное значение корня уравнения х = (x), а число q определяется из соотношения '(x) q < 1. Тогда справедливо соотношение (вывод см. ниже):

.

Если поставить условие, что истинное значение корня должно отличаться от приближенного значения на величину , т.е. - xn, то приближения x0, x1, … , xn надо вычислять до тех пор, пока не будет выполнено неравенство

или

и тогда = xn

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

Линейная система n уравнений может быть записана в виде:

a11x1 + a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2

. . . . . . . . . . .

an1x1 + an2x2 + … + annxn = bn

Эту систему линейных уравнений можно также записать в матричном виде:

,

где A - матрица коэффициентов системы, а и - вектор-столбец неизвестных и вектор-столбец правых частей соответственно.

.

3.1 Классификация СЛАУ

1. Если количество уравнений в системе больше количества неизвестных, то система называется переобусловленной. Если количество уравнений меньше количества неизвестных, то система называется недообусловленной.

2. Если система имеет хотя бы одно решение, она называется совместной. Система, не имеющая решений, называется несовместной.

3. Совместная система, имеющая единственное решение, называется определенной. Совместная система, имеющая бесконечное количество решений, называется неопределенной.

4. Если все коэффициенты правых частей системы равны нулю, то система называется однородной. Если хотя бы один из этих коэффициентов не равен нулю, то система называется неоднородной.

Однородная система уравнений всегда совместна, т.к. имеет хотя бы одно решение, xi = 0 (i=1,2,…,n), называемое тривиальным.

3.2 Обусловленность СЛАУ

Таким образом, малые погрешности вычислений или исходных данных могут привести к существенным погрешностям в решении. Такие системы уравнений называются плохо обусловленными.

Для оценки полученного решения используют следующее соотношение:

Произведение называется числом обусловленности матрицы A и обозначается как cond(A).

3.3 Метод Гаусса

Он основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы.

Сначала с помощью первого уравнения исключается х1 из всех последующих уравнений системы. Затем с помощью второго уравнения исключается х2 из третьего и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса, продолжается до тех пор, пока в левой части последнего (n-го) уравнения не останется лишь один член с неизвестным xn, т.е. матрица системы будет приведена к треугольному виду.

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных: решая последнее уравнение находят единственное неизвестное xn. Далее, используя это значение, из предыдущего уравнения вычисляют xn-1 и т.д. Последним находят значение х1 из первого уравнения.

a11x1 + a12x2 + a13x3 = b1

a21x1 + a22x2 + a23x3 = b2

a31x1 + a32x2 + a33x3 = b3

Для исключения х1 из второго уравнения прибавим к нему первое, умноженное на -а21/а11.

a11x1 + a12x2 + a13x3 = b1

(a22-а21/а11)x2 + (a23-а21/а11)x3 = b2-(а21/а11)b1

a31x1 + a32x2 + a33x3 = b3

Затем, умножив первое уравнение на -а31/а11 и прибавив результат к третьему уравнению, исключим из него х1

a11x1 + a12x2 + a13x3 = b1

(a22-а21/а11)x2 + (a23-а21/а11)x3 = b2-(а21/а11)b1

(a32-а31/а11)x2 + (a33-а31/а11)x3 = b3-(а31/а11)b1

Общие формулы пересчета коэффициентов при этом выглядят следующим образом:

a'ij = aij - (ai1/a11)a1j (i,j = 2,3)

b'i = bi - (ai1/a11)b1 (i = 2,3)

Т.е. система имеет вид

a11x1 + a12x2 + a13x3 = b1

a'22x2 + a'23х3 = b'2

a'32x2 + a'33x3 = b'3

Теперь из третьего уравнения системы надо исключить х2. Для этого надо умножить второе уравнение на -a'32/a'22 и прибавить результат к третьему. В результате получится

a11x1 + a12x2 + a13x3 = b1

a'22x2 + a'23х3 = b'2

a''33х3 = b''3

где a''33 = a'33 - (a'32/a'22)a'23 и b''3 = b'3 - (a'32/a'22)b'2 .

Матрица полученной системы имеет треугольный вид.

В процессе исключения неизвестных приходится выполнять операции деления на коэффициенты а11, а22 и т.д. Поэтому они должны быть отличными от нуля. В противном случае необходимо соответствующим образом переставить уравнения системы. Диагональные элементы матрицы обычно называют ведущими или главными элементами.

Обратный ход начинается с решения третьего уравнения системы

x3 = b''3/a''33.

Используя это значение, можно найти х2 из второго уравнения, а затем х1 из первого:

x2 = (b'2 - a'23x3)/a'22 ; x1 = (b1 - a12x2 - a13x3)/a11

Аналогично строится вычислительный алгоритм для линейной системы с произвольным числом уравнений. При этом расчетные формулы принимают вид:

Прямой ход метода Гаусса

, , где

k=1,2,…,n-1 ; i=k+1,k+2,…,n ; j=k+1,k+2,…,n.

В этих формулах k - номер неизвестного, которое исключается из оставшихся n-k уравнений (а также номер того уравнения, с помощью которого исключается xk); i - номер уравнения, из которого исключается неизвестное xk; j - номер столбца.

Обратный ход метода Гаусса

; , где i=n-1,n-2,…,1 .

В этих формулах i - номер неизвестного, которое определяется из i-го уравнения; j=i+1,i+2,… - номера уже найденных неизвестных.

3.4 Метод прогонки

Метод прогонки применяется для решения систем линейных уравнений с матрицей специального вида - трехдиагональной матрицей:

- ai xi-1 + ci xi - bi xi+1= fi, i=2, ... , n-1

x1 = k 1 x2 + n 1 (2)

xn = k 2 xn-1 + n 2

На первом этапе находятся коэффициенты

a i+1 = bi /(ci - ai a i) , b i+1 = (b i ai + fi ) /(ci - ai a i ) i=2, ... , n-1 (прямой ход), a 2 = k 1, b 2 = n 1,

а на втором этапе находится решение

xi = a i+1 xi+1 + b i+1 , i = n-1, ... ,2,1

xn = (n 2 + b n) / (1-a n k 2).

Для корректности метода прогонки достаточно, чтобы коэффициенты a i были по модулю меньше единицы, а выражения в знаменателях формул были отличны от нуля. Достаточные условия корректности прогонки формулируются в следующих теоремах.

Теорема Пусть система уравнений (2) такова, что ai > 0, bi > 0, ci > 0, ci і ai + bi , i=2,..., n-1, и пk 1п + пk 2п <2, пk 1п Ј 1, пk 2п Ј 1.

Тогда метод прогонки корректен.

Теорема Пусть система уравнений (2) такова, что ai > 0, bi > 0, ci > 0, ci і ai + bi, i=2,..., n-1, и существует i0 >1 такое, что ci0 > ai0 + bi0 , и п k 1п Ј 1, п k 2п Ј 1.

Тогда метод прогонки корректен.

Теорема Пусть система уравнений (2) такова, что зaiз , зbi з ,зci з >0, зci з > зaiз+...+зbi з , i=2,..., n-1, и п k 1п Ј 1, п k 2п Ј 1. Тогда метод прогонки корректен.

3.5 Метой простой итерации

Приведение системы к итерационной форме

Представить исходную систему уравнений

a11x1 + a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2

… … … … … … … … …

an1x1 + an2x2 + … + annxn = bn

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

x1 = c12x2 + c13x3 + … + c1nxn + d1

x2 =c21x1 + c23x3 + … + c2nxn + d2

… … … … … … … … … …

xn =cn1x1 + cn2x2 + cn3x3 +… + dn

где

В матричном виде итерационная система уравнений имеет вид



Выполнение итерации

В качестве начального приближения к решению может быть выбран произвольный вектор. Часто для этого используют вектор правых частей приведенной системы. Решение не зависит от выбора начального приближения, однако, чем ближе начальное приближение к точному решению, тем меньше итераций потребуется для решения системы с заданной точностью .

Вектор очередного приближения к решению рассчитывается по соотношению

или

Проверка условия окончания решения

Решение считается найденным, если два последовательных приближения оказываются достаточно близкими, т.е. норма вектора их разности сравнима с заданной точностью

3.6 Достаточное условие сходимости простой итерации

Если норма матрицы коэффициентов приведенной системы меньше единицы

,

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

Следует отметить, что процесс итераций заведомо сходится, если элементы исходной матрицы удовлетворяют условию

или элементы приведенной матрицы удовлетворяют условию

где n - число неизвестных системы.

Если все нормы матрицы больше единицы, то с помощью элементарных преобразований исходную систему нужно попытаться заменить эквивалентной, для которой условия сходимости выполняются. Эквивалентная система может быть получена перестановкой уравнений исходной системы или заменой отдельных уравнений линейной комбинацией других уравнений системы. Целью проводимых преобразований должно быть получение максимальных по модулю коэффициентов на главной диагонали матрицы коэффициентов.

3.7 Оценка погрешности n-приближения

Количество шагов при точности Е из условия:

||A||k+1||F||/(1-||A||)<E,

где F-вектор начальных приближений. Решение считается найденным, если два последовательных приближения оказываются достаточно близкими, т.е. норма вектора их разности сравнима с заданной точностью

3.8 Итерации Зейделя

Этот метод является модификацией метода простой итерации. Стратегия этого метода отличается тем, что при расчете элементов вектора наряду с элементами предыдущего приближения учитываются также и элементы, которые уже определены на данной итерации . Расчетная формула метода

3.9 Оценка обусловленности системы линейных уравнений

Таким образом, малые погрешности вычислений или исходных данных могут привести к существенным погрешностям в решении. Такие системы уравнений называются плохо обусловленными.

Для оценки полученного решения используют следующее соотношение:

3.10 Число обусловленности

Произведение называется числом обусловленности матрицы A и обозначается как cond(A).

3.11 Оценка погрешности решения

Решение считается найденным, если два последовательных приближения оказываются достаточно близкими, т.е. норма вектора их разности сравнима с заданной точностью

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

Многие практические задачи сводятся к решению системы нелинейных уравнений.

Пусть для вычисления неизвестных x1, x2, …, xn требуется решить систему n нелинейных уравнений:

F1(x1, x2, … , xn) = 0

F2(x1, x2, … , xn) = 0

. . . . .

Fn(x1, x2, … , xn) = 0

В отличие от решения СЛАУ не существует прямых методов решения систем нелинейных уравнений. Лишь в отдельных случаях эту систему можно решить непосредственно. Например, для случая двух неизвестных иногда удается выразить одно неизвестное через другое и таким образом свести задачу к решению одного нелинейного уравнения относительно другого.

В общем случае для решения систем нелинейных уравнений обычно используются итерационные методы.

4.1 Метод простых итераций

Пусть требуется найти действительные решения системы двух уравнений

F1(x,y) = 0

F2(x,y) = 0

с заданной точностью.

Для этого перепишем исходную систему в приведенном (итерационном) виде:

x = 1(x,y)

y = 2(x,y)

Пусть x0 и y0 - начальные приближения корней, полученные графическим или каким-либо другим способом. Подставив эти значения в правые части приведенной системы уравнений можно получить

x1 = 1(x0,y0)

y1 = 2(x0,y0)

Аналогично можно получить второе приближение

x2 = 1(x1,y1)

y2 = 2(x1,y1)

В общем случае

xn = 1(xn-1,yn-1)

yn = 2(xn-1,yn-1)

Если функции 1(x,y) и 2(x,y) непрерывны и последовательности x1, x2, … , xn, … и y1, y2, … , yn, … сходятся, то пределы их дают решение приведенной, а следовательно, и исходной системы.

Теорема об условиях сходимости итерационного процесса в этом случае выглядит следующим образом:

Пусть в некоторой замкнутой окрестности R (a x A, b y B) имеется одно и только одно решение x = x* и y = y* приведенной системы.

Тогда если:

1) функции 1(x, y) и 2(x, y) определены и непрерывно дифференцируемы в R;

2) начальные приближения x0, y0 и все последующие приближения xn, yn (n = 1,2, …) принадлежат R;

3) в R выполнены неравенства

или неравенства

то процесс последовательных приближений сходится к решению x = x*, y = y*.

Оценка погрешности n-го приближения определяется неравенством:

где M - наибольшее из чисел q1 и q2, входящих в эти неравенства.

4.2 Метод Ньютона

В основе метода Ньютона для системы уравнений лежит использование разложения функций Fi(x1, x2, … , xn) в ряд Тейлора, причем члены, содержащие вторые производные (и производные более высоких порядков), отбрасываются.

Пусть приближенные значения неизвестных системы (например, полученные на предыдущей итерации) равны соответственно а1, а2, … , аn .Задача состоит в нахождении приращений (поправок) в этим значениям x1, x2, … , xn , благодаря которым решение исходной системы запишется в виде:

x1 = a1 + x1 , x2 = a2 + x2 , , . . . . . , xn = an + xn.

Проведем разложение левых частей уравнений исходной системы в ряд Тэйлора, ограничиваясь лишь линейными членами относительно приращений:

. . . . . . . . . . . . . . . . . .

Поскольку левые части этих выражений должны обращаться в ноль, то можно приравнять нулю и правые части:



. . . . . . . . . . . . . . . . . .

Значения F1, F2 , … , Fn и их производные вычисляются при x1 = a1 , x2 = a2 , … , xn = an.

Определителем последней системы является якобиан:

Для существования единственного решения системы якобиан должен быть отличным от нуля на каждой итерации.

Таким образом, итерационный процесс решения системы нелинейных уравнений методом Ньютона состоит в определении приращений x1, x2, …, xn к значениям неизвестных на каждой итерации. Счет прекращается, если все приращения становятся малыми по абсолютной величине:

В методе Ньютона также важен удачный выбор начального приближения для обеспечения хорошей сходимости. Сходимость ухудшается с увеличением числа уравнений системы.

В качестве примера можно рассмотреть использование метода Ньютона для решения системы двух уравнений:

F1(x,y) = 0

F2(x,y) = 0

где F1 и F2 - непрерывно дифференцируемые функции.

Пусть начальные значения неизвестных равны a, b .

После разложения исходной системы в ряд Тэейлора можно получить:

Предположим, что якобиан системы при x = a и y = b отличен от нуля:

Тогда значения x и y можно найти, используя правило Крамера следующим образом:

и

Вычислив значения x и y можно найти следующие приближения неизвестных по формулам:

Величины, стоящие в правой части, вычисляются при x = a и y = b.

5. Интерполяция функций

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

.

Требуется по известным значениям

,

"восстановить", хотя бы приближенно, исходную функцию то есть построить на отрезке функцию , достаточно близкую к . Функцию принято называть интерполирующей функцией, точки - узлами интерполяции.

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

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

5.1 Постановка задачи

Выберем некоторую систему функций , заданных на отрезке , и будем строить как их линейную комбинацию:

,

где числовые коэффициенты подлежат определению, согласно условиям:

, .

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

,

или в развернутом виде:

.

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

.

Определение.

Система функций удовлетворяющая при фиксированных значениях условию , называется Чебышевской.

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

5.2 Формула Лагранжа

.

Перепишем этот полином в несколько другой форме, выделяя и в качестве множителей

.

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

Представим искомый полином в виде:

,

где полиномы степени , "ориентированные" на точки в том смысле, что

Такие полиномы легко построить:

или в развернутом виде:

Иногда нам будет удобно записывать в виде:

.

Из выражения и формул очевидно, что построенный полином действительно является интерполяционным полиномом для функции на сетке с узлами . Его принято называть интерполяционным полиномом в форме Лагранжа. Этим подчеркивается, что возможны и другие эквивалентные представления интерполяционного полинома . С одним из них мы познакомимся в следующем разделе.

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

5.3 Формула Ньютона

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

Перепишем интерполяционный полином Лагранжа в иной, эквивалентной форме

,

где - полиномы Лагранжа степени , соответствующие узлам интерполирования . В частности, - полином нулевой степени.

Полином

имеет степень и по построению обращается в ноль при поэтому его можно представить в виде

,

где - числовой коэффициент при . Поскольку не содержит степени , то просто совпадает с коэффициентом при в полиноме . Согласно и его можно записать в виде

,

Где

.

При этом

.

Формулы и позволяют написать рекуррентное соотношение для полинома :

.

Выражая аналогичным образом по индукции через , через и т. д., получим окончательную формулу для полинома :

Представление удобно для вычислителя, поскольку увеличение на единицу требует только добавления к "старому" многочлену одного дополнительного слагаемого. Такое представление интерполяционного полинома называют интерполяционным полиномом в форме Ньютона.

Из трех эквивалентных представлений интерполяционного полинома первой степени - формула дает его запись в форме Ньютона.

5.4 Оценка погрешности интерполяции

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

, .

Сразу же отметим, что по определению интерполяционного полинома

 при ,

поэтому речь идет об оценке при значениях .

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

В силу можно представить в виде:

,

где - полином степени :

.

Зафиксируем произвольное значение и рассмотрим вспомогательную функцию от переменной :

,

заданную на отрезке и содержащую переменную в качестве параметра. В силу своего определения функция обязана обращаться в нуль в узлах интерполирования при и кроме того при , т.е. как функция аргумента она имеет нуля:

, , .

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

Повторяя это рассуждение, заключаем, что имеет по крайней мере нулей на отрезке , - нуль и, наконец, обращается хотя бы один раз в нуль в некоторой точке , то есть

.

Учитывая, что производная полинома степени тождественно равна нулю, получаем, что

;

и соответственно

.

Формула не позволяет вычислить погрешность, поскольку точное значение аргумента нам неизвестно.

Однако с ее помощью погрешность можно оценить:

,

где

.

Обсудим роль полинома в оценке . На отрезке он имеет нуль, а его значения между этими нулями сравнительно невелики, но, когда точка выходит за пределы отрезка и удаляется от точки влево или от точки вправо, оценка ухудшается из-за быстрого роста функции . Это хорошо видно на рис. 2, где в качестве примера приведен график функции с корнями , , , :

.

Ее наибольшее по модулю значение на отрезке равно единице. Однако уже в точках за пределами отрезка полином принимает значение

.

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

5.5 Интерполяция сплайнами

Увеличение степени интерполяционного полинома может оказаться невыгодным из-за быстрого роста объема вычислений. К тому же далеко не всегда оно приводит к повышению точности. Во второй половине ХХ века с появлением компьютеров и развитием современной вычислительной математики при обработке больших таблиц получила развитие новая идея - строить приближение функций с помощью кусочно-полиномиальной интерполяции с использованием полиномов сравнительно невысоких степеней. Наиболее удобными оказались полиномы третьей степени. Такие конструкции получили название кубических сплайнов.

Определение кубического сплайна.

Пусть на отрезке задана функция . Рассмотрим сетку узлов

и обозначим через расстояние между смежными узлами

,

Определение:

Назовем кубическим сплайном функции , на сетке функцию удовлетворяющую условиям:

S1. На каждом отрезке функция является полиномом третьей степени.

S2. Функция , её первая и вторая производные непрерывны на сегменте .

S3.

S4. На концах сегмента функция удовлетворяет условиям .

Замечание. На концах сегмента могут быть заданы в принципе и другие условия, например:

.

Справедлива следующая теорема.

Теорема.

Существует единственный сплайн , удовлетворяющий требованиям (S1) - (S4).

Мы проведем конструктивное доказательство этой теоремы.

Формулировка системы уравнений для коэффициентов кубического сплайна.

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

, .

При этом, очевидно:

,

,

так, что

.

Для выполнения требований (S3) в узлах интерполяции с номерами следует положить:

Требуя непрерывности сплайна в узлах и выполнения условия (S3) при , получим:

Или

.

Это равенство можно переписать следующим образом:

.

Условие (S2) непрерывности первой производной в узлах принимает вид:

и приводит к соотношениям

Или

.

Аналогичным образом условия непрерывности второй производной в тех же узлах:

означают, что

.

Наконец, дополнительные граничные условия (S4) дают еще два уравнения

.

В итоге мы получили замкнутую систему , , , , содержащую в сумме линейных уравнений для отыскания неизвестных:

6. Аппроксимация функций

6.1 Постановка задачи

Иногда возникает необходимость аппроксимации данной функции другими функциям, которые легче вычислить. В частности, рассматривается задача о наилучшем приближении в нормированном пространстве Н, когда заданную функцию f требуется заменить линейной комбинацией заданных элементов из Н так, чтобы отклонение ||f - || было минимальным.

6.2 Метод наименьших квадратов

Mетод наименьших квадратов был предложен Гауссом и Лежандром в конце XVIII - начале XIX веков в связи с проблемой обработки экспериментальных данных. В этом случае задача построения функции непрерывного аргумента по дискретной информации , характеризуется двумя особенностями:

1. Число точек , в которых проводятся измерения, обычно бывает достаточно большим.

2. Значения функции в точках сетки определяются приближенно в связи с неизбежными ошибками измерения.

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

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

,

погрешность уравнение интерполяция

в частности, возможен вариант .

Предположим, что мы каким-то образом выбрали коэффициенты , тогда в каждой точке сетки , можно подсчитать погрешность

.

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

.

Она дает количественную оценку того, насколько близки значения функции в точках сетки к величинам .

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

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

Функцию с набором коэффициентов, удовлетворяющих этому требованию, называют наилучшим приближением по методу наименьших квадратов.

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

Необходимым условием экстремума является равенство нулю в экстремальном точке всех первых частных производных рассматриваемой функции. В случае это дает

.

Оставим члены, содержащие , слева и поменяем в них порядок суммирования по индексам и . Члены, содержащие , перенесем направо. В результате уравнения примут вид

,

где

,

.

Мы получили систему линейных алгебраических уравнений , в которой роль неизвестных играют искомые коэффициенты разложения . Число уравнении и число неизвестных в этой системе совпадает и равно . Матрица коэффициентов системы Г состоит из элементов , которые определяются формулой . Ее называют матрицей Грама для системы функций на сетке . Отметим, что матрица Грама является симметричной: для ее элементов, согласно , справедливо равенство . Числа , стоящие в правой части уравнений , вычисляются по формуле через значения сеточной функции .

Предположим, что функции выбраны такими, что определитель матрицы Грама, отличен от нуля:

.

В этом случае при любой правой части система имеет единственное решение

.

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

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

Квадрат погрешности и точке для функции с коэффициентами можно записать в виде

Здесь в среднем слагаемом мы заменили в одной из сумм индекс суммирования на , чтобы не использовать один и тот же индекс в двух разных суммах и иметь возможность перемножить их почленно.

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

Рассмотрим теперь сумму вторых слагаемых, которые зависят от линейно:

Здесь мы поменяли местами порядок суммирования и воспользовались тем, что коэффициенты , удовлетворяют системе уравнений .

С учетом будем иметь

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

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

7. Численное интегрирование

Пусть на отрезке [a,b] задана функция y = f(x). С помощью точек x0, x1, … , xn отрезок [a,b] можно разбить на n элементарных отрезков [xi-1, xi] (i=1,2,…,n), причем x0 = a, xn = b. На каждом из этих отрезков можно выбрать произвольную точку xi (xi-1 Ј xi Ј xi) и найти произведение si значения функции в этой точке f(xi) на длину элементарного отрезка Dxi = xi - xi-1:

si = f(xi) Dxi .

Теперь можно составить сумму всех таких произведений:

Сумма Sn называется интегральной суммой. Определенным интегралом от функции f(x) на отрезке [a,b] называется предел интегральной суммы при неограниченном увеличении числа точек разбиения; при этом длина наибольшего из элементарных отрезков стремится к нулю:

7.1 Формулы прямоугольников, трапеций, парабол (Симпсона). Оценки погрешностей

Методы прямоугольников

Этот метод непосредственно использует замену определенного интеграла интегральной суммой. В качестве точек xi могут выбираться левые (xi = xi-1) или правые (xi = xi) границы элементарных отрезков. Обозначая f(xi) = yi и Dxi = hi, можно получить следующие формулы метода прямоугольников.

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

,

где xi-1/2 = (xi-1 + xi) / 2 = xi-1 + hi /2 , i=1,2,…,n

Этот алгоритм обычно называют методом средних.

Если применяют постоянный шаг интегрирования hi = h = const, то последняя формула принимает вид:

Предельная абсолютная погрешность метода прямоугольников:

, где

Погрешность решения составляет 1.2192-1.219=0.0002 (около 0.016%)

Погрешность метода:

На отрезке [1,2] производная достигает наибольшего значения f'(x) = 0.5 в точке x=1. Таким образом М1 = 0.5. Тогда по формуле погрешности можно получить

Отсюда можно убедиться, что во всех случаях точное решение находится в интервале полученное решение ± 0.05.

Метод трапеций

Этот метод использует линейную интерполяцию, т.е. график функции y = f(x) представляется в виде ломаной, соединяющей точки (xi, yi). В этом случае площадь всей фигуры (криволинейной трапеции) складывается из площадей элементарных прямолинейных трапеций.

Площадь первой трапеции (s1) равна

Аналогично:

. . . . . . . . . . . .

и, следовательно,

Отсюда, учитывая, что yk = f(xk), можно получить исходную формулу метода трапеций:

где cj = 1, 2, 2, … , 2, 1 .

Чем больше n, тем точнее, при прочих равных условиях, данная формула. Исключение составляет лишь тот очевидный случай, когда функция f(x) линейна, тогда формула дает точные результаты при n = 2.

Предельная абсолютная погрешность метода трапеций:

, где

Погрешность метода:

Таким образом, на отрезке [ 1,2 ] получим Ѕf''(x)Ѕ Ј 1/4 = 0.25. Тогда по формуле:

В общем случае погрешность Rn численного значения Sn равна

Она зависит от шага разбиения, и ее можно представить в виде Rn = O(hk). В случае переменного шага можно принять h = max(hi) .Из этого представления погрешности численного интегрирования следует, что при h ® 0 (n ® Ґ) значения интеграла, получаемые путем численного интегрирования, сходятся к его точному значению.

На основании формул прямоугольников и трапеций можно получить уточненные значения интегралов, если учесть характер погрешностей этих формул. Главный член погрешности формулы прямоугольников (по среднему) на каждом отрезке [xi-1, xi] равен h3 * f IV(xi - 1/2)/24; для формулы трапеций он равен -h3 * f''(xi)/12, т.е. примерно вдвое больше и имеет другой знак. На основании этого можно записать уточненную формулу для вычисления определенного интеграла с использованием значений I1 и I2, вычисленных по методам прямоугольников и трапеций:

I » (2I1 + I2)/3.

Для рассмотренного выше примера получено I1 = 1.2192, I2 = 1.2184. Поэтому

I = (2*1.2192 + 1.2184)/3 = 1.2189.

Т.е. с точностью до погрешности округления все разряды равны точным значениям.

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

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

Метод парабол

В этом методе вершины каждых трех ординат соединяются дугами квадратичных парабол, оси которых параллельны оси y. Таким образом, вместо двух прямоугольных трапеций рассматривают одну элементарную трапецию, ограниченную параболической дугой. Исходя из этого можно видеть, что число разбиений n в методе Симпсона должно быть четным.

Площади полученных трапеций можно обозначить как s12, s34, … , sn-1,n. Рассмотрим первую из этих трапеций. Для упрощения вычислений можно перенести ось ординат параллельно самой себе так, чтобы она шла вдоль ординаты yo . Ясно, что от этого величина площади не изменится.

Уравнение квадратичной параболы, ось которой параллельна оси y, есть

y = A0 + A1*x + A2*x2

Чтобы парабола проходила через точки подынтегральной кривой (xo,yo), (x1,y1), (x2,y2) нужно правильно подобрать коэффициенты А0, А1 и А2:

Так как xo = 0, x1 = h и x2 = 2h, то, подставив эти значения в приведенное выше уравнение можно получить:

После решения этой системы можно найти:

; ;

Площадь s12 определяется интегралом:

Подставив найденные значения А0, А1 и А2 в это уравнения и приведя свободные члены, получим:

Аналогично

. . . . . . . . . .

Следовательно,

Отсюда можно найти формулу метода парабол (или метода Симпсона):

Или, в более компактном виде:

где cj = 1, 4, 2, 4, 2, … ,2, 4, 1 .

Предельная абсолютная погрешность метода Симпсона:

, где

8. Методы решения задачи Коши для обыкновенного дифференциального уравнения

1.1. Опр. Пусть дан отрезок [a,b]. Равномерной сеткой на этом отрезке назовем множество узлов w h такое, что w h = { xj = jh, j=0,...,n, h=(b-a)/n) }.

Опр. Сеточной функцией y = yj = y(xj) называется функция, заданная в узлах сетки.

Любую сеточную функцию y j = y(xj) можно представить в виде вектора Y=(y0, y1, ..., yn-1, yn), и, следовательно, множество сеточных функций образует конечномерное пространство, в данном случае размерности n+1. В этом пространстве можно ввести норму, например или .

Пусть дано дифференциальное уравнение Lu(x) = f(x,u) ( например, ) .

1.2. Заменим Lu в узле сетки xi линейной комбинацией значений сеточной функции yi на некотором множестве узлов сетки, называемом шаблоном. Такая замена Lu на Lh yh называется аппроксимацией на сетке дифференциального оператора L разностным оператором Lh . Замена непрерывной функции f(x,u) в узлах сетки на сеточную функцию j (xh,yh) называется аппроксимацией правой части.

Таким образом дифференциальное уравнение можно аппроксимировать (заменить) на сетке разностной схемой

Lh yh = j (xh,yh) (например, ).

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

Пусть uh - проекция непрерывной функции u(x) на сетку (например, uh = u(xj) = uj).

Опр. Погрешностью аппроксимации дифференциального оператора Lu разностным оператором Lh назовем величину

y 1 = (Lu)h - Lh uh,

где (Lu)h - проекция на сетку результата действия дифференциального оператора L на функцию u

(например,).

Опр. Говорят, что погрешность аппроксимации дифференциального оператора имеет в узле xi порядок k , если y 1(xi) = O(hk) 0 при h0.

Опр. Погрешностью аппроксимации правой части f сеточной функцией j h назовем величину y 2 = fh - j h , где fh - проекция на сетку функции f(x,u) (например, f(xj ,uj).

Опр. Погрешность аппроксимации правой части имеет в узле xi порядок m , если y 2 = O(hm) 0 при h 0

Опр. Погрешностью аппроксимации разностной схемы на решении в узле xi (локальной погрешностью) назовем величину y , равную

y = y 1 - y 2 = (Lu)h - Lh uh - (fh - j h)= j h - Lh uh,

здесь использовано, что Lu=f.

.

Опр. Значения локальной погрешности аппроксимации в каждом узле xi образуют сеточную функцию погрешности аппроксимации y i .

Обычно требуется оценка погрешности аппроксимации на сетке, т.е. оценка функции y i в некоторой сеточной норме.

Опр. Говорят, что погрешность аппроксимации разностной схемы имеет m-ый порядок на сетке, если чкyчк = O(hm).

Опр. Решение разностной схемы сходится к решению дифференциального уравнения с порядком k на сетке, если погрешность решения

ч к zh ч к =ч к uh - yh ч к = O(hk) ® 0 при h® 0.

8.1 Метод Рунге-Кутты 4-ого порядка точности

На практике широко распространен Метод Рунге - Кутта четвертого порядка:

Данная схема имеет четвертый порядок аппроксимации.

9. Методы оптимизации функций

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых параметров, определяющих данную задачу. При решении задач эти параметры обычно называют переменными или факторами оптимизации. Их число (x1, x2, … , xn) определяет размерность задачи оптимизации.

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

Целевую функцию в общем виде можно записать следующим образом

u = f(x1, x2, …, xn)

Различают одно- и многофакторную оптимизацию. В случае однофакторной оптимизации целевая функция является функцией одной переменной, и ее график - некоторая кривая на плоскости. При n=2, например, целевая функция является функцией двух переменных, и ее графиком является поверхность.

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

Задачи оптимизации. Можно выделить два типа задач оптимизации - безусловные и условные.

9.1 Обусловленность задачи поиска минимума

Будем искать минимум функции f(x), которая определена на отрезке [a,b] и унимодальна (т.е. на данном отрезке имеет только один минимум).

Процесс решения задачи методом поиска состоит в последовательном сужении интервала изменения фактора оптимизации, называемого интервалом неопределенности. В начале процесса оптимизации его длина равна b-a, а к концу она должна стать меньше заданного допустимого значения , т.е. оптимальное значение параметра оптимизации должно находиться в интервале неопределенности - отрезке [xn, xn+1], причем xn+1 - xn < .

...