Численные методы алгебры icon

Численные методы алгебры




Скачать 180.66 Kb.
НазваниеЧисленные методы алгебры
Дата конвертации30.06.2012
Размер180.66 Kb.
ТипДокументы
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)
§ модифицированные функции бесселя
§ функции бесселя дробного порядка
Математическая обработка экспериментальных данных (введение в математическую статистику)
Функции
§ классификация по одному признаку
Бу­дет иметь
Математическая обработка
§ выбор эмпирических формул для анализа нелинейных зависимостей
Гармонический анализ экспериментальных данных
§ корреляционный анализ экспериментальных данных
Математическая обработка экспериментальных данных (специальные методы анализа)
§ метод буркова
 для исходных ве­личин Х
§ Спектральный анализ временных рядов
Литератур а

Глава 1. ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ

§ 1. ЭЛЕМЕНТАРНАЯ АЛГЕБРА


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

1.1. КОМПЛЕКСНАЯ АРИФМЕТИКА. ИЗВЛЕЧЕНИЕ КОРНЕЙ n -й СТЕПЕНИ ИЗ КОМПЛЕКСНОГО ЧИСЛА


При извлечении корней n-й степени из ком­плек­с­­но­­­го чис­ла z = x + iy = reii2 = - 1), где x = Re z - дей­ст­ви­тель­ная часть; y = Im z - мнимая часть; y = |z| = - мо­дуль; arg z - глав­ное зна­­­чение ар­гу­мен­та комплексного числа, ис­поль­­­зу­ется фор­му­ла Му­ав­ра:



При этом алгоритм пред­по­ла­га­ет вычисление n кор­ней уравнения zn = x + iy. Область при­ме­не­ния его оче­вид­­на - это задачи, связанные с ком­п­лек­сной арифмети­кой.

Формальные параметры процедуры. Входные: x, y (тип real) - действительная и мни­мая части ком­плек­с­но­го числа; n (тип integer) - по­ка­­затель сте­пени. Вы­ход­ные: од­но­мер­ные массивы Re[1:n], Im[1:n], в ко­то­рых запо­ми­на­­ют­ся соответственно действительные и мни­мые час­ти комплексных корней.

Алгоритм реализован в следующей про­це­ду­ре:

Procedure Croot (x,y: real; N: integer;

var re, im : mas1);

const pi = 3.14159265;

var a, m, r, t : real; i : integer;

Begin m:=1/n;

r := EXP((m/2) *ln (x*x+y*y));

if x=0 then t := sign(y)*pi/2;

if x>0 then t := arctan(y/x) else

t := arctan(y/x)+pi;

t := m*t; a:=2*pi*m;

for i:=1 to n do

begin

re[i]:=s*cos(t);

im[i]:=s*sin(t);

t:=t+a;

end;

End { *** Croot *** };

Точность вычислений по данной подпрограмме оп­ре­­­де­ля­ется точностью пред­став­ле­ния дейст­ви­тель­ных чи­­сел в ис­пользуемой ЭВМ и точ­нос­тью вы­чис­ле­ния фун­­кций sin и cos в со­от­вет­ству­ющ­их биб­ли­о­те­ках под­про­­грамм.

Подпрограмма тестировалась на примерах из­вле­­че­­ния кор­ней 3-й и 5-й степени из комплекс­ных чи­­­сел z1 = 8 + i6 и z2 = - 8 + i6 (выбор чисел оп­ре­­­де­лялся тре­бо­ва­ни­ем срав­ни­мости результа­тов с вы­­чис­лениями по ана­ло­­гичной про­це­дуре, опи­сан­ной Аге­евым и др. (1976) ). Ре­зультаты рас­че­­­тов пред­ставлены в табл. 1.1.

Дан­ные результаты совпадают с ре­зуль­та­та­ми ра­­бот Аге­ева и руч­но­го счета с точ­нос­тью 10 - 6.

Замечание. В работе Нестора [Nestor, 1961] в целях эко­но­­мии ма­шинного времени при n > 3 предлагает­ся вмес­то об­ра­­щения к стандартным функциям sin и cos в цикле ис­поль­­зовать рекуррентные фор­му­лы (1.1):

(1.1)

что, однако, требует некоторых дополнительных за­трат памяти ЭВМ [Агеев и др., 1976]. По оцен­кам специалистов [Nestor, 1961] такая процедура ока­зы­ва­ет­ся весь­ма эф­фек­тивной в задачах, связанных с раз­ло­же­нием в ряд Фурье, как это было предложено в работе [Goerzel, 1961].

Таблица 1.1

формула расчета

xn = 8 + i 6

xn = — 8 + i 6

n = 3

x = 2.1050612 + i 0.4585914

x = — 1.4496824 + i 1.5937408

x = — 0.6553788 — i 2.0523322

x = 1.4496824 + i 1.5937408

x = — 2.1050612 + i 0.4585914

x = 0.6553788 — i 2.0523322

n = 5

x = 1.5717854 + i 0.2034135

x = 0.2922507 + i 1.5577150

x = — 1.3911645 + i 0.7593073

x = — 1.1520377 — i 1.0884372

x = 0.6791661 — i 1.4319985

x = 1.3911646 + i 0.7593073

x = — 0.2922507 + i 1.5577150

x = — 1.5717854 + i 0.2034135

x = — 0.6791661 — i 1.4319985

x = 1.1520377 — i 1.0884372

Од­­на­ко наши расчеты, вы­пол­ненные на ком­пь­ю­те­ре РC/AT-286 с частотой 12 МГц, показали, что сколь­ко-ни­будь зна­чи­тель­но­го выигрыша во времени ис­поль­зование ре­кур­рен­т­ных со­от­но­шений (1.1) пра­к­­тически не дает.

1.2. КОМБИНАТОРИКА. БИНОМ НЬЮТОНА И РОДСТВЕННЫЕ ФОРМУЛЫ


Число перестановок из n элементов опре­де­ля­ет­ся формулой

Pn = n! ; (1.2)

число размещений из n элементов по m элементов

; (1.3)

число сочетаний из n элементов по m элементов

. (1.4)

Число перестановок с повторениями (корте­­жа­ми) со­ста­ва (спецификации) (k1, k2, ..., kr ) опре­де­ля­ется фор­му­лой

; (1.5)

число сочетаний из n элементов по m с повторени­­я­ми

. (1.6)

При чис­лен­­ных расчетах также можно ис­поль­зо­вать рекуррентную формулу

. (1.7)

В формулах (1.2) - (1.4) n!, m!, k! и (n-m)! - фак­то­­ри­а­лы, которые легко могут быть вы­чис­ле­ны­ из опре­де­ле­ния

0! = 1, n > 0. (1.8)

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

при n ® Ґ . (1.9)

Относительная ошибка фор­­мулы Стирлинга, как это видно из выражения (1.9), убы­ва­­ет с воз­рас­танием n. Для до­статочно больших n, од­на­ко, бо­лее точ­но­го ре­зуль­тата можно до­­би­ть­ся, ес­ли ис­поль­зовать спе­циальную фор­­мулу [Корн, Корн, 1978]:

, (1.10)

поскольку ; при n ® Ґ. От­ме­­чен­ные особенности учтены нами в процедуре вы­чис­ле­ния факториала, ко­­то­рая мо­жет быть с успехом ис­поль­зована для на­­­хож­дения в со­от­вет­ст­вии с форму­ла­ми (1.2) - (1.6).

Формальные параметры процедуры. Входные: n (тип integer) - натуральное число, фак­­ториал ко­то­ро­­го тре­бу­ется вычислить; k (тип integer) - ключ, зна­чение ко­то­ро­го отвечает выбо­ру одной из формул (1.8) - (1.10): k < 0 - формула (1.8), k = 0 - фор­мула (1.9), k > 0 - формула (1.10). Вы­ходной: идентификатор процедуры-функ­ции fct (тип real)- значение факториала.

{*** fct ***}

Function fct (n, k : integer) : real;

const pi = 3.14159265;

var s1, s2, s3 : real; i : integer;

begin

if n=0 then

begin

fct:=1;

exit;

end;

if k < 0 then

begin

fct:=1;

for i:=1 to n do

fct:=fct*i;

exit;

end;

s1:=sqrt(2*pi*n);

if k=0 then

begin

s3:=0;

s2:=0

end

else

begin

s3:=1/(360*n*n*n);

s2:=1/(12*n)

end;

fct:=exp(n*ln(n))*s1*exp(-n+s2-s3);

end .

Оценка точности вычислений проводилась при тес­ти­­ровании программы для n = 5,­ 10, ­15, ­20, 30;­ k = -1, 0, 1. Результаты, полученные при n = 5, 10, ­15, и со­от­вет­с­т­­­­вующие им величины от­но­си­тель­ной по­греш­­ности пред­­­ставлены в табл.1.2.

Результаты те­с­­­­тирования по­ка­зы­вают, что с рос­­том n по­греш­ность вычисления n! умень­­ша­ет­ся, при­чем во всех слу­­чаях формула (1.10) да­ет бо­лее точ­ный ре­зуль­тат. Од­нако следует отметить, что при дальнейшем уве­ли­­чении n погрешность фор­му­лы (1.10) остается прак­­тически на том же уров­не (~1.0 e - 5 %) и при не­об­хо­димости по­лучить бо­лее точ­ный результат тре­бу­ется удер­жать сле­ду­ю­щий член в разложении (1.10). Даль­ней­­ший рост n при­водит к появлению оши­бок округ­ле­­ния, свя­зан­­­ных с ко­­неч­нос­тью раз­ряд­­ной сет­ки ЭВМ.


Таблица 1.2

n

Формула (1.8) (точное значение)

Формула (1.9)

Формула (1.10)

5

120

118.019172668 (1.65 %)

119.9999771 (1.9 e - 5 %)

10

3628800

3598695.75 (0.82 %)

3628800 (0 %)

15

1307674279936

1300430716928 (0.55 %)

1307674411008 (1.0 e - 5 %)




Процедура fct мо­жет быть эф­­фек­тив­но ис­поль­­зо­­вана при вы­числении би­но­­ма Ньютона:

(1.11)

и величины полинома

, (1.12)

где суммирование проводится по всем наборам не­от­ри­ца­тельных целых чисел (k1 ,k2 ,...,kr ), для ко­то­рых k1 + k2 + +... + kr = n. При этом Cn (k1, k2, ..., kr), вы­чис­ляемые по фор­муле (1.5), на­зываются по­ли­но­­ми­аль­ными ко­эф­фи­ци­ен­та­­ми. Формула для определения количества по­­ли­но­ми­аль­ных ко­эф­фи­ци­ен­тов имеет вид:

.

Рассмотрим процедуру-функцию вы­чис­­­­ле­ния би­­но­ма Ньютона, в которой используется функ­ция fct в со­от­вет­ст­вии с формулой (1.11).

Формальные параметры процедуры. Входные: a, b (тип real)- значения слагаемых a и b в вы­ра­же­нии (1.11); n (тип integer) - показатель степени би­­но­­­ма; k (тип in­te­ger) - ключ, определяющий вы­бор ал­­­го­рит­ма вы­чис­ле­ния фак­то­ри­ала (см. опи­са­ние па­­­ра­мет­ров процедуры-функции fct). Вы­­ход­ной: функ­ция binn (тип real) - зна­­чение би­нома Нью­то­­на.

Function binn (var a, b : real;

var n, k : integer;): real;

var s,f1,f2,f3 : real; l,m : integer;

begin

bin:=0;

f1:=fct(n,k);

for l:=0 to n do

begin

f2:=fct(l,k);

m :=n-l;

f3:=fct(m,k);

s :=f1/(f2*f3);

bin:=bin+s*exp(a*ln(m)+b*ln(l));

end;

end; {*** binn ***} .

Оценка точности вы­чис­ле­ний бинома про­­во­­ди­­лась при те­с­тировании про­грам­мы для n = 5, 10, 15, 20, 30; k = - 1 (дан­ное зна­чение k со­от­вет­­ству­ет точ­­но­му вы­чис­ле­­нию фак­то­риала в про­це­ду­ре-функ­­­ции fct) и раз­лич­­ных па­ра­мет­ров a и b. Результаты, по­лу­чен­ные при n = 5, 7, 10, 15; a = =1.5; b = 2.5, -2.5, и со­­от­вет­с­т­­­­ву­­ющие им ве­ли­чи­ны от­­­но­си­­тель­­ной по­греш­ности пре­д­­­став­­ле­­ны в табл. 1.3.

Таблица 1.3

Параметр

Значение бинома при ис­поль­зовании формулы

n

a

b

(1.8)

(1.10)

5


7


10


15


1.5


1.5


1.5


1.5


2.5

- 2.5

2.5

- 2.5

2.5

- 2.5

2.5

- 2.5

1024 (+ 0%)

— 1 (+ 0%)

16384 (+ 0%)

— 1 (+ 0%)

1048576 (+ 0%)

1.00098 (+9.766e-2%)

21073741696 (+1.2e-5%)



1024.1940 (+1.89e-2%)

— 0.8770 (+11.3%)

16385.5449 (+9.4e-3%)

0.125 (+112.6%)

1048610 (+3.2e-3%)



1073747328 (+5.1e-4%)







Из таблицы вид­­но, что при b > 0 с уве­ли­че­ни­ем n точ­ность вычислений рас­тет и практически ог­ра­­ни­чена толь­ко ошиб­­ка­ми округления, для от­­ри­ца­тель­ных же b уже при n>10 в случае ис­поль­зо­вания формулы (1.8) и при n ~ 5 в слу­чае ис­поль­зо­вания формулы (1.10) для фак­ториала по­греш­­ность рез­ко возрастает, что свя­зано с вычитанием боль­­­ших чисел в правой час­ти равенства (1.11). По­этому при b < 0 ре­ко­мен­ду­ется ис­поль­зо­вать эле­мен­тар­ную фор­му­­лу (a + b)n, на со­вре­мен­ных быст­ро­дей­ст­ву­ю­щих ЭВМ это даст не­ко­то­рый вы­и­грыш во времени счета.

Заметим, что совершенно аналогично может быть по­стро­е­­на процедура вычисления величины по­­­­ли­но­ма (1.12), по­э­то­­му она здесь не при­во­дит­ся.

Когда известно некоторое сочетание из n по m, тог­­да вы­­числение следующего по порядку соче­та­­­ния мо-

­жет быть эффективно осуществлено с по­­­мощью про­це­ду­ры генератора сочетаний [Аге­ев и др., 1976], которая об­ра­зу­ет следующее по по­­ряд­ку сочетание из n целых чи­сел по m, ес­ли за­да­ны n, m и пред­шес­т­в­у­ющее со­че­та­ние.

Формальные параметры процедуры. Входные: n, m (тип integer); вектор j [1:m] (тип integer) - пред­шес­­т­ву­ю­щее сочетание. Выходной: тот же вектор j, в котором це­лые числа ме­­няются от 0 до n - 1 и всегда при входе и вы­хо­де из процедуры со­став­ля­ют мо­но­тон­ную стро­го воз­­рас­тающую по­­­сле­до­ва­тель­­ность. Если вход­ной век­тор j сос­­то­ит из нулей, то в качестве пер­вого сочетания бу­дет по­­лучено (n - m, ..., n - 1). Та­кое же сочетание по­лу­­чит­­ся и пос­­ле со­четания (0, 1,..., k - 1), являющегося по­­след­ним зна­­­чением вектора j в этом цикле.

procedure comb (n, m : integer; var j : mas1);

var a, b, l : integer;

begin

for b:= 1 to m do

if j[b]>b then

begin

a:=j[b]-b-1;

for l:=1 to b do j[l]:=l+a;

exit;

end;

b:=n-m-1;

for l:=1 to k do

j[l]:=b+l;

end; {*** comb ***}.

Данный алгоритм был переведен авторами с язы­­ка AL­GOL на язык PASCAL и проверен на ма­ши­­не IBM PC/AT-286 для тех же значений вход­ных па­раметров, что и в работе Агеева и др. (1976), n = 4, k = 3. В ка­чес­т­ве на­чального вектора j был вы­б­ран вектор (0,0,0). В ре­­зультате по­сле­до­ва­­тель­­ных об­ра­щений к процедуре по­­лу­чены сле­­ду­ющие со­че­та­ния: (1,2,3), (0,2,3), (0,1,3), (0,1,2), что пол­нос­тью соответствует ре­зуль­та­там тести­ро­­­вания AL­GOL-программы, при­ве­ден­ными в ра­бо­те Аге­­­ева и др. (1976).

1.3. ВЫЧИСЛЕНИЕ СИМВОЛА ЯКОБИ


Символ Якоби - функция, определяемая для всех це­­лых a, взаимнопростых, с заданным не­четным це­лым чис­­лом P > 1. Так, если P = p1 p2 ...pr - раз­ло­же­ние чис­ла P на простые сомножите­ли не обязательно раз­­лич­ные, то

,

где - символы Лежандра [Виноградов, 1953], т.е. ариф­­метические функции чисел a и рi , опре­де­ленные для прос­­тых нечетных рi и целых а, не де­лящихся на P, при­­чем = 1, если срав­не­ние x2 є a(mod pi) раз­ре­ши­­мо, а в про­­тив­ном случае = -1. Часто символ Ле­­­жанд­ра, а сле­д­­о­ва­тельно, и символ Якоби, который яв­ля­ется его обоб­щением, доопределяют для чисел a, де­ля­­щих­­ся на pi (для символа Якоби соответственно на P), по­­лагая, что в этом случае = 0. Символ Яко­би об­ладает свой­ст­ва­ми, ана­ло­гич­ны­ми свойствам сим­во­ла Ле­жанд­ра, а имен­но:

  1. если a є b (mod P), то = ;

  2. = 1;

  3. ;

  4. = .;

  5. ,

    где P, Q - по­­ло­­­жи­тель­ные нечетные взаимно простые чис­ла (квад­­­ра­тич­ный закон взаимности, который впервые до­ка­зан для сим­во­ла Лежандра Гауссом в 1876 г.);

  6. ;

  7. .

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

Процедура syjac, построенная по алгоритму, учи­­­ты­ва­­­ющему приведенные свойства, вы­чис­­­­ляет зна­че­­ние сим­во­ла Якоби по квадра­тич­­­­ному за­ко­ну вза­­имности. При этом полагает­ся сле­­дующее (таб­л. 1.4):

Таблица 1.4

Условие

Значение сим­во­ла Якоби ...

P - четное

Не опре­де­­лено

P - не­­чет­ное

2

P - простое и a является квад­­ра­тич­ным невычетом числа m

- 1

Если a и P име­ют не­три­ви­аль­ный общий множитель

0

Ос­т­аль­ные случаи

1

Формальные параметры процедуры. Входные: a, p (тип integer). Выходной: r (тип integer) - зна­че­ние сим­во­ла Якоби.

procedure syjac (a, p : integer; var r : integer);

var k : integer; z, q : boolean;

label : start, cycle;

Function parity (x:integer): boolean;

{ *** значение функции parity true, если х -

четное, и false - в противном случае *** }

begin

if (x div 2 * 2) = x then

parity := true

else

parity := false;

еnd; {***parity***}

begin

start:

if not parity (p) then

begin

r := 2:

exit;

end;

z := true;

cycle:

repeat

a:=a - a div p * p;

q := false;

if a > 1 then

begin

while not parity (a) do

begin

q:= not q;

a:=a div 2;

end;

if q and parity ((sqr(p)-1) div 8) then

Z := not Z;

if a  1 then

begin

if parity((p-1)*(a-1) div 4) then

z:= not z;

k:=p;

p:=a;

a:=k;

end;

until a <= 1;

if a=0 then

r:= 0

else

if z then

r := 1

else

r:= -1;

end.

Приведенный алгоритм был переведен ав­то­ра­­ми с язы­ка ALGOL на язык PASCAL и проверен на ма­­ши­­не IBM PC/AT-286 для тех же значений вход­­ных па­ра­мет­ров, что и в работе Агеева (1976). В ре­зуль­тате тес­ти­ро­ва­ния было получено:

= 1 (a = 5 - квадратичный вычет);

= -1 (a = 3 - квадратичный невычет);

= 2 (p = 12 - четное), что полностью со­от­вет­с­т­­ву­­ет результатам тести­ро­­ва­ния программы на языке ALGOL, приведен­ным в работе Агеева и др. (1976).

1.4. РАЗЛОЖЕНИЕ МНОГОЧЛЕНА

НА МНОЖИТЕЛИ


Многочлен (целая рациональная функция) от­но­си­тель­но x1 ,x2 ,..., xm есть сумма конечного чис­ла чле­нов вида , где каждое kj - це­лое не­от­ри­ца­тель­ное чис­ло. Наибольшее зна­че­ние сум­мы k1 + k2 + ...+ km, встре­чающееся в ка­ком­­-либо из чле­нов, называется сте­пенью мно­го­чле­­на. В про­стей­шем слу­чае, когда x1 = x2 = =...= xm = x и наибольшее зна­че­ние суммы сте­пе­ней , мно­го­­член принимает вид

. (1.13)

Выражение (1.13) называется канонической фор­­мой представления целой рациональной функ­ции. Ес­ли многочлен (1.13) при n > 1 мо­жет быть пред­став­лен в виде про­изведения мно­гочле­нов низ­ших степеней, он на­зы­ва­ет­ся при­водимым. Воз­мож­ность разложения на мно­жи­те­ли мно­го­чле­нов сте­пе­ни n > 1 зависит от об­лас­ти опре­деле­ния ко­­э­ф­фи­ци­ен­тов. В частном случае, ког­­да об­ласть опре­де­ле­ния ко­­эф­фициентов есть мно­жес­тво дейс­т­­ви­тельных чи­сел, любая целая ра­цио­наль­ная функ­­ция n-й степени мо­­жет быть раз­ложена на мно­жи­тели первой и вто­рой степени (ос­­новная те­о­­­рема ал­геб­ры [Бронштейн, Се­­мендяев, 1981] ). При­веденная на­ми процедура fac­tors позволяет най­ти все ра­ци­о­наль­ные ли­ней­ные мно­­жители (uix+vi), 1 < i < r мно­­го­чле­на (1.13) в част­­ном случае, ког­да область опре­де­ле­­ния ко­­эф­фи­ци­­ентов сужена до множества целых чи­сел. При этом на­хо­дит­ся так­же наибольший об­щий де­ли­тель c ко­­эф­фи­циен­тов ai. Суть метода сос­тоит в том, что на­­­хо­дя­тся все делители p ко­эф­фи­циента a0 и все де­ли­­тели q ко­эф­фи­циента an, (при­чем 1 < p < |a0| и 1n|). Да­лее со­с­тавляются все возможные па­ры из найден­ных p и q и про­­ве­ря­ется, не яв­ля­ет­ся ли дву­­член (px - q) мно­жи­те­­лем мно­гочлена.

Формальные параметры процедуры. Входные: n (тип in­­teger)- степень многочлена; a[0:n] (тип in­te­ger) - массив ко­­эффициентов мно­го­­члена. Вы­ход­ные: u[1:r], v[1:r] (тип in­teger) - массивы коэф­фи­ци­ен­тов со­­­от­вет­ствен­но при пер­вых и нулевых степенях x в ра­­­ци­о­нальных линейных мно­жи­телях; r (тип integer) - количество ли­ней­ных мно­жи­те­лей в раз­­ло­жении мно­го­чле­на; c (тип integer) - на­и­боль­ший об­щий де­ли­тель коэф­фи­циентов ai мно­го­чле­на.

Procedure factors (n : integer; a : mas1;

var u,v : mas1; var r,c : integer);

label zero;

var i, f, g, p, q : integer;

begin

r:=0;

c:=1;

{ *** в блоке с меткой zero исключаются

множители вида (1*x-0) *** }

zero:

if a[n]=0 then

begin

n:=n-1;

r:=r+1;

u[r]:=1;

v[r]:=0;

goto zero;

end; { *** zero***}

for p:=1 to abs(a[0]) do

if (a[0] div p * p) = a[0] then

begin

{ *** найдено значение p, являющегося

делителем коэффициента a0 ***}

for q:=1 to abs(a[n]) do

begin

{ *** ищется q  0, являющийся множителем an ***}

if q<>1 then

repeat

if (a[n] div q * q)=a[n] then

begin

{ *** выполняется проверка, не является ли

q общим множителем для всех a i ***}

for i:=0 to n do

if (a[i] div q * q) = a[i] then

for i:=0 to n do

a[i]:=a[i] div q;

c := c * q;

end

until (a[n] div q * q)<>a[n];

{ *** выполняется проверка, не является ли (px-q)

множителем многочлена; ***}

repeat

f:=a[0];

g:=1;

for i:=1 to n do

begin

g:=g*p;

f:=f*q+g*a[i]

end;

if f=0 then Inc(r);

{***двучлен (px-q) является множителем.

Делим на него наш полином ***}

u[r]:=p;

v[r]:=q;

for i:=0 to n do

begin

a[i]:=f:=(a[i]+f) div p;

f:=f*q;

end;

n:=n-1;

if n=0 then

begin

c:=c*a[0];

exit

end

else

q:=-q;

until (n<>0) or (q<0);

end;

if n=0 then c:=c*a[0];

end.

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

P3 є 3x3 - 29 x2 + 78x - 40 = 1*(x - 4) (x - 5) (3x - 2);

P3 є x3 - 6x2 + 32 = 1*(x + 2) (x - 4) (x - 4).

1.5. ВЫЧИСЛЕНИЕ КОРНЕЙ ПОЛИНОМОВ С ЦЕЛЫМИ КОЭФФИЦИЕНТАМИ В ФОРМЕ ПРОСТЫХ ДРОБЕЙ


Число xj называется корнем (нулем) целой ра­­ци­о­­­наль­ной функции f(x) с действительными ко­­э­ф­­фи­­ци­ен­­тами, ес­ли

. (1.14)

Вычисление корней полиномов, таким об­ра­зом, сво­дится к решению алгебраических урав­не­ний (1.14). Для на­хождения рациональных кор­ней по­­ли­но­­мов с це­лы­ми ко­эф­фициентами обыч­но ис­поль­зу­ет­­ся хорошо из­вес­тная схе­ма Горнера [Корн, Корн, 1978; Бронштейн, Семендяев, 1981]. В алгоритме при­ме­не­но пред­ло­жен­ное в работе [Pek, 1961] рас­ши­ре­ние этой схе­мы, суть ко­­то­­рого сос­то­ит в сле­­ду­ю­щем. По­ли­ном (1.13) с це­лы­­ми ко­эф­фи­ци­ен­тами при a0Ч an 0 име­ет в ка­чест­­ве кор­ня не­со­кра­ти­мую дробь p/q тог­да и толь­­­ко тогда, когда

.

Кроме того, q должно быть множителем an, а p - мно­жителем a0. Ненулевые рациональные кор­ни p/q мо­­гут

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

Формальные параметры процедуры. Входные: a (тип in­teger) - одномерный массив размером от 0 до n, в ко­то­ром размещают коэффициенты по­­ли­но­ма (1.13); n (тип in­te­ger) - степень по­ли­но­ма; k (тип string) - имя фай­ла на внеш­нем носителе (маг­нит­ном дис­ке), в ко­то­рый будут за­пи­сываться ре­зуль­таты сче­та. Вы­ход­ные: p, q (тип integer) - чис­ли­тели и зна­ме­­­на­те­ли найденных ра­ци­ональ­ных кор­ней, вы­во­дя­т­­ся на внешний но­ситель.

procedure ratf (a : mas1; var n : integer;

k: string);

var i, p, q, r, t, f, g, a0, an : integer; f : text;

begin

a0:=abs(a[0]);

an:=abs(a[n]);

Assign (f,k);

Rewrite (f);

for p:=1 to a0 do

begin




Похожие:

Численные методы алгебры iconДокументы
1. /Мак-Кракен Д.Численные методы и программирование на Фортране.1977.djvu
Численные методы алгебры iconСписок примерных экзаменационных задач по курсу «Численные методы»
Высота h и радиус основания цилиндра r измерены с точностью 5 %. Какова относительная
Численные методы алгебры iconМосковский департамент образования лицей №1533 (информационных технологий)
Сам алгоритм был реализован фирмой Intel®, заказчик решил использовать его в курсе «Алгоритмы и численные методы», читаемого в Лицее,...
Численные методы алгебры iconДокументы
1. /Info.txt
2. /Численные методы.DOC

Численные методы алгебры iconДокументы
...
Численные методы алгебры iconВопрос 19. Методы математической статистики в педагогических исследованиях
Появляясь, новые методы сразу привлекают к себе пристальное внимание специалистов
Численные методы алгебры iconМетоды, приёмы самостоятельной работы учащихся на уроках…
Словесный, наглядный методы: использование карточек, вопрос – ответ, взаимоопрос в парах, взаимооценка, самооценка…
Численные методы алгебры iconМетоды, приёмы самостоятельной работы учащихся на уроках…
Словесный, наглядный методы: использование карточек, вопрос – ответ, взаимоопрос в парах, взаимооценка, самооценка…
Численные методы алгебры iconМетоды организации учебной деятельности учащихся Методы по характеру познавательной деятельности

Численные методы алгебры iconДокументы
1. /Новые методы/AP_FILE.doc
2. /Новые методы/int13ext(rus).doc
Численные методы алгебры iconМетоды исследования белков
Все методы разделения смесей основаны на том, что разделяемые компоненты в результате каких-либо манипуляций оказываются в разных...
Разместите кнопку на своём сайте:
Документы


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