If (a0 div p p) = a0 then icon

If (a0 div p p) = a0 then




Скачать 413.67 Kb.
НазваниеIf (a0 div p p) = a0 then
страница1/6
Дата конвертации30.06.2012
Размер413.67 Kb.
ТипРешение
  1   2   3   4   5   6
1. /1E_PAG.DOC
2. /GLAV1.DOC
3. /GLAV12.DOC
4. /GLAV13.DOC
5. /GLAV14.DOC
6. /GLAV21.DOC
7. /GLAV22.DOC
8. /GLAV234.DOC
9. /GLAV256.DOC
10. /GLAV31.DOC
11. /GLAV32.DOC
12. /GLAV33.DOC
13. /GLAV34.DOC
14. /GLAV35_.DOC
15. /GLAV36.DOC
16. /GLAV37.DOC
17. /GLAV39.DOC
18. /GLAV412.DOC
19. /GLAV42.DOC
20. /GLAV43.DOC
21. /GLAV45.DOC
22. /GLAV51.DOC
23. /GLAV52.DOC
24. /GLAV5345.DOC
25. /GLAV55.DOC
26. /GLAV56.DOC
27. /GLAV57.DOC
28. /GLAV61.DOC
29. /GLAV62.DOC
30. /GLAV63.DOC
31. /GLAV645.DOC
32. /GLAV71.DOC
33. /GLAV72.DOC
34. /GLAV734.DOC
35. /GLAV75.DOC
36. /GLAV81.DOC
37. /GLAV83.DOC
38. /GLAV84.DOC
39. /GLAV9.DOC
40. /LITRUCOV.DOC
В. Ю. Белашов, Н. М. Чернова эффективные алгоритмы и программы вычислительной математики
Численные методы алгебры
If (a0 div p p) = a0 then
§ Методы решения систем линейных и нелинейных уравнений
§ Алгебра матриц
Интерполирование и экстраполирование функций
§ Построение интерполяционного полинома Ньютона по заданным значениям функции Окончание таблицы 2
§ интерполяция по эйткену
§ Полиномиaльная аппроксимация производных любого порядка таблично заданной функции личивается и количество не­об­хо­ди­мых вы­числений, что де­ла­ет метод три­го­но­мет­­ри­чес­кой ин­тер­поляции не со­всем удоб­ным
Численное дифференцирование и интегрирование
§ Численное интегрирование по простейшим формулам
Формальные параметры процедуры
= 1 получаем формулу трапеций
§ Интегрирование с автоматическим выбором количества узлов методом рунге
§ Интегрирование с автоматическим выбором количества узлов
§ Вычисление интеграла по Ромбергу
§ Вычисление комплексного криволинейного интеграла
Приближенные методы интегрирования обыкновенных дифференциальных уравнений и систем
Вычисляют
{ Процедура "метод Эйлера с уточнением" }
Формальные па­ра­мет­ры процедуры
Специальные функции и алгоритмы их вычисления
§ Некоторые интегральные функции
§ неполные эллиптические интегралы I и II рода
§ Функции Бесселя целого порядка jnx01:=exp (n*ln(x1))*(exp (n*ln 5))+s)
§ модифицированные функции бесселя
§ функции бесселя дробного порядка
Математическая обработка экспериментальных данных (введение в математическую статистику)
Функции
§ классификация по одному признаку
Бу­дет иметь
Математическая обработка
§ выбор эмпирических формул для анализа нелинейных зависимостей
Гармонический анализ экспериментальных данных
§ корреляционный анализ экспериментальных данных
Математическая обработка экспериментальных данных (специальные методы анализа)
§ метод буркова
 для исходных ве­личин Х
§ Спектральный анализ временных рядов
Литератур а

§ 2. Решение нелинейных алгебраических уравнений с одной переменной

{ *** если p и q не являются множителями ко­эффициентов соответственно a[0] и a[n], переходим на конец цикла для продвижения в соответствующем списке цикла ***}

if (a0 div p * p) = a0 then

begin

for q:=1 to an do

begin

if (an div q * q) = an then

begin

{*вычисление полинома для проверки, является ли p/q корнем, при этом определение значения r дает экономию одного вычисления переменной с индексом ***}

f := a[0];

g := a[0];

t := p;

for i:=1 to n do

begin

r := a[i]*t;

f:=f*q+r;

g:=-g*q+r;

t:=t*p

end;

if f=0 then

write (f,p:10:5,' ',k:5,q:10:5);

if g=0 then

write (f,p:10:5,' ',k:5,q:10:5);

end;

end; {**q**}

end;

end; {**p**}

end.

Процедура, в которой пре­д­став­лен ис­прав­лен­ный, ординарно пе­ре­ра­бо­тан­ный и мо­ди­фи­ци­ро­ван­ный ал­го­­ритм [Perry, 1962], пе­­­ре­ве­де­на ав­то­ра­ми с язы­ка AL­GOL [Агеев и др., 1976] на язы­к PAS­CAL с со­хра­нением ори­­ги­­наль­ного син­­так­си­са про­цедуры и проверена на ма­­ши­не IBM PC/AT-286 для тех же полиномов, что и в ука­­­зан­­ной выше ра­боте :

. При этом были получены результаты, полнос­тью сов­падающие с результатами Агеева и др. [1976]:

для : x1 = - 1/3, x2 = 3/4, x3 = - 3/9;

для : x1 = 1/2, x2 = - 1/3, x3 = 3/4, x4 = 3/6 .

Из результатов тестирования процедуры вид­но, что во втором случае x4 = x1, и, кроме того, вы­­­да­ется из­бы­точ­ное значение корня p/q, в котором p и q со­держат об­щий мно­жи­тель (это было также от­ме­­че­но в работе [Hal­ste­ad, 1962] для ал­­го­рит­ма Перри [Perry, 1962] ).

§ 2. РЕШЕНИЕ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ С ОДНОЙ ПЕРЕМЕННОЙ


Нелинейное алгебраическое уравнение с од­ной пе­­­ременной в общем случае может быть за­пи­са­но в виде

F(x) = 0, (1.15)

где функция F(x) определена и непрерывна на ко­­неч­ном или бесконечном интервале a < x < b.

Вся­кое зна­чение [a, b], обращающее функ­цию F(x) в нуль, т.е. когда F() = 0, называется кор­­нем урав­­не­­ния (1.15) или нулем функции F(x). Чис­­­ло  на­­зывается кор­­нем k-й кратности, ес­ли при x  вмес­­те с функцией F(x) равны нулю и ее про­­из­вод­­ные до порядка (k - 1) вклю­чительно:

F(x) = F'(x) = ... = F(л - 1)(x) = 0.

Однократный корень называется простым. Два урав­нения называются равносильными (эк­ви­ва­­­ле­н­т­­ны­ми), если множества их решений сов­па­да­­ют. Не­ли­нейные уравнения с одной пе­ре­мен­ной под­раз­­де­ля­ются на алгебраические, когда функ­­ция F(x) в фор­муле (1.15) яв­ляется алгебраической, и транс­­­цен­ден­тные в про­тив­ном случае. Боль­шин­­ст­во ал­­геб­ра­и­чес­ких и тран­с­цен­ден­тных не­ли­ней­ных уравнений вида (1.15) ана­ли­ти­­чес­ки (т.е. точ­но) не решается, поэтому на прак­­тике для на­­хож­де­ния корней часто ис­поль­зу­ют­­ся численные ме­то­­ды. Рассмотрим не­ко­то­рые из них [Березин, Жидков, 1962; Бахвалов, 1973а, 1973б и др.].

Задача численного нахождения дейст­ви­тель­ных и ко­м­плексных корней уравнения [1.15] обы­ч­­но сос­­то­ит из двух этапов: отделения кор­ней, т.е. на­хож­де­ния до­ста­точно малых ок­рест­ностей рас­­смат­­ри­ва­е­мой об­лас­ти, в которых со­держится од­­но значение кор­ня, и уточ­не­ния кор­­ней, т.е. их вы­числения с за­дан­ной сте­пенью точ­ности в не­­ко­то­рой ок­рест­нос­ти. В свя­­зи с этим рас­смот­­рим вна­чале задачу от­де­ле­­ния кор­ней, а затем ряд ите­рационных ме­то­дов их уточнения.

2.1. ЗАДАЧА ОТДЕЛЕНИЯ КОРНЕЙ. УТОЧНЕНИЕ КОРНЕЙ МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ (МЕТОД ДИХОТОМИИ)


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

  1. отделения корней, т.е. устано­вле­­ния ин­тер­ва­ла , где содержится один и толь­ко один ко­­рень урав­­нения;

  2. задачи уточнения одним из известных ме­­то­дов най­ден­ного корня  с за­дан­­­ной погрешностью .

Предположим теперь, что найден от­ре­зок [а, b] та­­­кой, что F(а)F(b) < 0. Тогда, согласно те­­о­ре­ме Боль­ца­но-Коши [Бахвалов, 1973б], внут­ри от­рез­ка [а, b] су­щес­т­ву­ет точка , в которой F() = 0. Да­­лее не­об­хо­димо убе­дить­ся, что най­ден­­ная точка  единс­т­вен­ная на от­рез­ке [а, b]. Од­­ним из методов яв­ляется де­ле­ние отрезка на не­сколь­­­ко частей, на­при­­мер на че­ты­ре, и проверка на кон­­цах каждого из от­рез­ков зна­ка функции.

Нули функции на практике вычисляют при­бли­­­жен­­­но несколькими способами. Одним из са­мых рас­­­про­стра­ненных и не очень точных яв­ля­ет­ся гра­фи­­­ческий ме­тод, заключающийся в том, что F(х) пред­­­ставляют как F(х) = =(х) + (х), где (х) и (х) бо­лее простые по срав­нению с F(х) функ­­­ции. Да­лее стро­ят два гра­фи­ка y = (х); y = (х) и оп­ре­деляют точки их пе­ре­се­че­ния. Этим ме­­тодом вы­год­но решать уравнения вида хn + ах + b = 0 или ах + b + sin(сх)= = 0 и т.п. Но следует пом­нить, что этот метод дает лишь грубое при­бли­жение ре­ше­­ния.

Другим, не менее распространенным яв­­ляется ме­тод про­изводных. Он за­клю­ча­­ет­ся в том, что ищут и при­рав­ни­ва­­ют к нулю про­­изводную функ­ции F'(х). Затем на от­рез­ках рас­смат­ри­вают знак функ­­­ции F'(х), где хi - корни урав­не­ния F'(х) = 0. Таким об­­­ра­­­зом, всю чис­ло­вую ось раз­бивают на два ин­тервала и бо­­лее. Этот ме­тод еще называют ме­то­­дом экст­ремумов функ­ции.

Если исследуемая функция представлена по­ли­но­­мом n-й степени, то используют метод удаления кор­­­ней: опре­де­ля­ют один корень, и по теореме Ви­ет­­­та функ­цию F(х) пред­ставляют как F(х) = g(х)(х - х1), где x1 - пер­вый най­ден­ный корень, а g(х) - полином сте­пени (n - 1). Для про­вер­ки кратности корня x1 сле­­ду­­ет подставить в g(х), и если g(x1) = 0, то го­во­рят, что x1 является крат­ным корнем, а F(х) за­пи­­сы­ва­ет­­ся F(х) = g(х)(х - x1)2, где g(х) - те­перь по­ли­ном сте­­пени (n - 2). Следуя этому про­цес­­су, мож­но уда­лить все корни, т.е. пред­ста­вить

.

Чтобы погрешность с каждым шагом не уве­ли­чи­­ва­лась, а очередной корень определялся с вы­со­кой сте­пенью точности, следует уточнение корня де­­лать по F(х), а не по g(х). Это особенно важ­но, когда удалено мно­го (больше по­ло­ви­ны) корней.

Hа практике пред­по­ла­­га­емые корни уточняют раз­­лич­ными спе­ци­аль­ны­­ми вычислительными ме­то­­дами. Од­ним из них можно назвать ме­тод ди­хо­то­­мии (би­­сек­ции, по­ло­вин­ного деления), от­но­ся­щий­ся к ите­­ра­ци­он­ным. Он сос­то­ит в по­стро­е­нии по­­­сле­­до­ва­тель­ности вло­жен­ных от­рез­ков, на кон­­цах ко­то­рых F(х) имеет разные зна­ки. Каж­дый по­­­сле­­ду­ю­щий от­ре­зок получают де­ле­ни­­ем по­по­лам пре­ды­ду­­ще­го. Этот процесс по­стро­е­ния по­­­сле­­до­­ва­тель­нос­ти вло­жен­ных отрезков по­зво­ляет най­­­ти нуль функ­ции (F(х) = 0) с лю­бой за­дан­ной точ­­­ностью.

Опишем подробно один шаг итерации. Пусть на k-м ша­ге найден отрезок [аk , bk], на концах ко­­то­рого F(х) меняет знак. Заметим, что обязательно [аk, bk]  [а, b]. Разделим те­перь отрезок [аk, bk] пополам и вы­де­­лим F(), где  - се­ре­ди­­на [аk , bk]. Здесь воз­мож­­ны два слу­чая: первый, ког­да F() = 0, тогда мы го­ворим, что ко­рень найден; вто­рой, ког­да F() № 0, тог­да срав­­ниваем знак F() с F(аk) и F(bk) и из двух по­­ло­­вин [аk, ] и [, bk] вы­бираем ту, на концах ко­то­рой функ­ция меняет свой знак. Та­ким образом, аk = а , bk = , если F()F(аk) < 0 , и аk = , bk = b, ес­ли F()F(bk) < 0.

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

Метод дихотомии — простой и надежный ме­тод по­­­ис­ка простого корня1 уравнения F(х) = 0. Он схо­дит­ся для лю­бых непрерывных функ­­ций F(х), в том чис­ле и не­­диф­фе­рен­ци­ру­е­мых. Недостатки метода:

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

  2. если корней на выделенном отрезке не­сколь­ко, то нельзя заранее сказать, к какому из них сой­­­дет­ся про­цесс;

  3. не применим к корням четной крат­нос­ти;

  4. для корней нечетной, но высокой кратности ме­­­тод неустойчив, дает большие ошибки;

  5. медленно сходится. Для достижения  не­­об­­хо­димо выполнить N итераций2, т.е. для по­лу­че­­ния 3 верных цифр ( = 0.0005) на­до вы­полнить около 10 ите­­раций, ес­ли отрезок имеет единичную длину.

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

  1. Определить входные параметры А, В, ЕРS.

  2. Присвоить: А1 А; В1 В; К  0.

  3. Присвоить: Х1  А1; Х2  В1; К К + 1; Х3 (В1+А1)/2.

  4. Если F(Х1) ґ F(Х3) < 0, то перейти на шаг 5 ина­че на шаг 7.

  5. Присвоить: В1  Х3.

  6. Если | А1 - В1| < ЕРS, то перейти на шаг 10 ина­­че на шаг 3.

  7. Если F(Х2) ґ F(Х3) < 0, то перейти на шаг 8 ина­­­че на шаг 11.

  8. Присвоить: А1 Х3.

  9. Перейти на шаг 6.

  10. Печать: Х3 - корень уравнения; К - ко­ли­чес­тво ите­­­раций.

  11. | А1 - В1| / 2 - погрешность решения.

  12. Конец программы.

Это наиболее простое решение задачи, но не са­­мое эф­фективное. Эффективность можно по­вы­сить, если:

  1. заменить произведения F(х1F(х3) и F(х2F(х3) на ис­­поль­зование встро­ен­ной функции sign(х, у). В тех вер­си­ях язы­ка, где нет этой встро­­ен­ной функции, мож­но заранее на­­пи­­­сать со­­­от­вет­ст­ву­ю­щую про­це­ду­ру;

  2. определить процедуру-функцию, вы­чис­ля­ю­щую F(х) толь­­ко один раз;

  3. заменить в операторе цикла медленный оператор (А+В)/2 на более быстрый (А+В)*0.5. Заметим, что имен­­но для этой про­­грам­мы дан­ное усо­вер­шен­ство­ва­­­ние бу­дет не­за­мет­но, хотя в случае боль­ших про­­грамм учет скорости вы­пол­­­нения опе­ра­ций в ма­шине да­ет ощу­­­ти­мый ре­з­­уль­тат.

Формальные параметры процедуры. Входные: a, b (тип real) - определяют длину от­рез­­ка; eps (тип re­­al) - оп­ределяет заданную точ­ность вы­числений; it (тип in­te­ger) - определяет на­и­боль­­шее раз­ре­шен­ное количество ите­раций (для из­бе­жа­ния за­цик­ли­ва­­­ния про­цесса в слу­чае не­пра­виль­ного опре­де­ле­ния от­рез­ка). Выходные: х (тип real) - в нем со­дер­жит­­ся ис­комый ко­рень срав­не­ния; k (тип integer) - в не­го за­носится количество вы­пол­нен­ных ите­­ра­ций.

Учитывая все замечания, окон­ча­тель­­­­ный ва­риант про­це­­дуры bisect может быть сле­­­ду­ющим:

procedure bisect (a,b,eps :real; it:integer;

var x : real; var k:integer);

var a1, b1: real; x1, x2, x3 : integer;

begin

k := 0;

x1 := sign (func(a));

x2 := sign (func(b));

a1 := a;

b1 := b;

repeat

inc (k);

x := (a1+b1)*0.5;

x3 := sign (func (x));

if x3=0 then exit;

if abs(b1-a1)<(2*eps) then exit;

if (x1=x2) and (x2=x3) then exit;

if x1=x3 then

begin

a1 := x;

x1 := x3;

end

else

begin b1 := x;

x2 := x3;

end;

until k>it;

end.

Перед началом работы программы опре­­­деляют func(x) - процедуру-функцию, по которой вы­чис­ля­­­­ют зна­­­че­ния F(х). Тип функции должен быть ве­­щес­­­твен­ным. Ес­ли в библиотеке стан­дарт­но­го ма­те­­­матического ­обес­­пе­че­­­ния отсутствует про­це­ду­ра-функ­ция sign, то ее сле­дует на­­пи­сать самостоятельно.

Предложенная процедура проверялась на при­­­­­­м­е­ре ре­ше­ния уравнения x2 - 5 sin x = 0.

Графическим методом находился от­ре­зок, на ко­­­­­­то­ром рас­­полагался один из корней дан­ного урав­­­­­­­­нения [1.57; 3.14]; (второй ко­рень три­­­ви­аль­ный, х = 0 на­хо­дит­ся лег­ко). Для того, что­бы най­­­ти корень на отрезке [1.57; 3.14] с ука­­зан­ной точ­нос­тью, полагали ерs = 0.0005.

Результаты проверки работы предлагаемой про­­­­­­­­­цедуры при­водятся в табл. 1.5.

Таблица 1.5

Отрезок

Номер

Левый конец

Правый конец

Центральная точка

итерации

А

sign (А)

В

sign (В)

x

sign (x)

k

1.0

— 1

4.0

+1

2.5000




0

1.000000

— 1

2.500000

+1

1.750000

+1

1

1.750000

— 1

2.500000

+1

2.125000

+1

2

1.750000

— 1

2.125000

+1

1.937500

— 1

3

1.937500

— 1

2.125000

+1

2.031250

— 1

4

2.031250

— 1

2.125000

+1

2.078125

— 1

5

2.078125

— 1

2.125000

+1

2.101563

— 1

6

2.101563

— 1

2.125000

+1

2.089844

+1

7

2.101563

— 1

2.089844

+1

2.083984

+1

8

2.101563

— 1

2.083984

+1

2.086914

— 1

9

2.086914

— 1

2.083984

+1

2.085449

+1

10


Окончаниие таблицы 1.5

Отрезок

Номер

Левый конец

Правый конец

Центральная точка

итерации

А

sign (А)

В

sign (В)

x

sign (x)

k

2.086914

— 1

2.085449

+1

2.086182

— 1

11

2.086182

— 1

2.085449

+1

2.085815

+1

12

2.085815

— 1

2.086182

+1

2.085999

— 1

13

2.085815

— 1

2.085999

+1

2.085907

+1

14

2.085815

— 1

2.085907

+1

2.085953

— 1

15

2.085907

— 1

2.085953

+1

2.085930

+1

16

2.085930

— 1

2.085953

+1

2.085941

— 1

17

РЕШЕНИЕ: Х = 2.085936; F(x) = 0.0000066938; К = 18



  1   2   3   4   5   6

Похожие:

If (a0 div p p) = a0 then iconСодержание введение Структура html документов
Текстовые блоки H1, h6 p div address blockquote br hr pre listing, plaintext, xmp
If (a0 div p p) = a0 then iconAssolux 09/04/2006г
Каньшина Н. (Иркутск), вл. Транькова exo аs 23 : Blue Silver Mackerel Tabby exotic: tabby div
If (a0 div p p) = a0 then iconДокументы
1. /amp.pdf
2. /avto&div.pdf
3.
If (a0 div p p) = a0 then iconДокументы
1. /Базовые задачи на обработку массива.doc
2. /ЗадачиНаЛиниВетвление.doc
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©znanie.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы