Лекции по методам оптимизации - файл n1.doc

Лекции по методам оптимизации
скачать (1278 kb.)
Доступные файлы (1):
n1.doc1278kb.29.05.2012 23:54скачать

n1.doc

  1   2   3   4   5   6   7   8

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

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

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

а = А - а .

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

 = А - а .

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

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

 = А - а  а .

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

.

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

.
1.2.Основные составляющие абсолютной погрешности.

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

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

(a b) = a + b .

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

;

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



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

u = x1 + x2

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



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

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

  1 + 2 + ... + n .

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

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

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

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

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

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



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





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

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) непрерывной, можно найти:



или

= ().

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

0

Y=x

Y=(x)

Y=x

Y=(x)

y

y











X0

X1

X2

X0

X1

X2

X3


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



X0

X1

X2

y

X

Y=x


(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.6.)

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) .

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



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



X0

X1

y

F(x0)

B

B=x0

a

0




, (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 можно составить пропорцию (см.рисунок)



Откуда



b

B

f(b)

a

A


x



x

y

0




Далее, применяя этот прием к тому из отрезков [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  

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

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

a11x1 + a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2

. . . . . . . . . . .

an1x1 + an2x2 + … + annxn = bn

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

,

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

.
  1   2   3   4   5   6   7   8


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации