3. Степенные многочлены

3.0. Введение

Степенным многочленом (полиномом) называют функцию вида

где a_i - действительный коэффициент,
x - действительная или комплексная переменная,
n - степень многочлена.

В бейсик-программе многочлен может быть представлен в виде вектора коэффициентов {a_i}, i=0...n.

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

Раздел содержит широкий набор алгоритмов обработки многочленов.

3.1. Вычисление значений

Быстрый способ вычисления значений многочлена - схема Горнера:

Программа 23. Случай действительного аргумента.

10 INPUT "n",A:FOR B=0 TO A:PRINT A-B;:INPUT E(B):NEXT B
20 INPUT C:D=0:FOR B=0 TO A:D=D*C+E(B):NEXT B:PRINT D:GOTO 20

Размер: 68, E(n)

Пример: P(x)=3x³+2x²+x; x=0,1.

Программа 24. Случай комплексного аргумента.

10 INPUT "n",A:FOR B=0 TO A:PRINT A-B;:INPUT H(B):NEXT B
20 INPUT "Re",C,"Im",D:E=0:F=0:FOR B=0 TO A:G=C*E-D*F+H(B)
30 F=C*F+D*E:E=G:NEXT B:PRINT "Re";E,"Im";F:GOTO 20

Размер: 116, I(n)

Пример: P(x)=3x³+2x²+x; x=0,1+j0,2.

3.2. Оценка устойчивости

Все корни многочлена степени n

отрицательны только в том случае, если то же выполняется для многочлена степени n-1

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

Программа 25. Критерий Рауса - Гурвица. В случае подтверждения устойчивости программа выдает сообщение "У.", неустойчивости - "Не". Следует выделить случай, когда на какой-либо итерации a₁=0. Программа выдает номер шага i, после чего прерывается, либо (если i≥n-1) выдает результат. Если результат "Не", неустойчивость доказана. При любом другом исходе необходимо ввести в член a_i малое возмущение a_i Ь a_i + d и провести счет заново.

10 INPUT "n",A:FOR B=0 TO A:PRINT B;:INPUT E(B):NEXT B
20 FOR B=0 TO A:IF E(B)<0;PRINT "Не":GOTO 10
30 IF E(B)=0;PRINT B;
40 IF B>A-3 THEN 70
50 IF F(B)=0;PRINT B+1:GOTO 10
60 D=E(B)/F(B):FOR C=B TO A-3 STEP 2:G(C)=G(C)-D*H(C):NEXT C
70 NEXT B:PRINT "У.":GOTO 10

Размер: 161, E(n)

Пример 1: P(x)=2x⁴+3x³+x²+5x+1.

Пример 2: P(x)=12x⁵+12x⁴+16x³+10x²+5x+1.

3.3. Арифметические операции над многочленами

Программа 26. Перемножение многочленов.

10 VAC :INPUT "n",A:FOR B=0 TO A:PRINT B;:INPUT F(B):NEXT B
20 INPUT "m",C:FOR D=0 TO C:PRINT D;:INPUT E:FOR B=0 TO A
30 G(A+B+D)=G(A+B+D)+E*F(B):NEXT B:NEXT D:FOR B=0 TO A+C
40 F(B)=G(A+B):G(A+B)=0:PRINT B;F(B):NEXT B:A=A+C:GOTO 20

Размер: 147, G(2*n+m)

Пример: P(x)=(4+3x+2x²+x³)(x+2x²)(x+2x²).

Программа 27. Деление многочленов.

где делимое P_n(x) и делитель Q_m(x) - исходные данные,
а частное T_n-m(x) и остаток R_m-1(x) - результаты.

10 INPUT "m",A:FOR B=0 TO A:PRINT A-B;:INPUT E(B):NEXT B
20 INPUT "n",C:FOR B=0 TO C:PRINT C-B;:INPUT F(A+B):NEXT B
30 FOR B=A TO C:F(B)=F(B)/E:PRINT C-B;F(B)
40 FOR D=1 TO A:F(B+D)=F(B+D)-E(D)*F(B):NEXT D:NEXT B
50 FOR B=C-A+1 TO C:PRINT "R";C-B;F(A+B):NEXT B

Размер: 166, F(m+n)

Пример: P₅(x)=2x⁵+5x⁴+8x³+11x²+4x; Q₂(x)=2x²+x.

Программа 28. Общий множитель двух многочленов. Два многочлена P₁(x) и P₂(x) могут быть представлены в виде

где R(x) - общий множитель;
Q₁(x), Q₂(x) - взаимно простые многочлены.
R(x) определяется по алгоритму Евклида.

Для приближенных вычислений следует изменить условие в строке 80. (Например, при использовании условия ABS H(A+C-E)<1E^-5 все коэффициенты, по модулю меньшие 10^-5, будут считаться нулевыми.)

10 INPUT "m",A:FOR B=0 TO A:PRINT A-B;:INPUT G(B):NEXT B
20 INPUT "n",C:FOR B=0 TO C:PRINT C-B;:INPUT H(A+B):NEXT B
30 IF A>C;E=C:GOTO 80
40 FOR B=A TO C:H(B)=H(B)/G
50 IF A>0;FOR D=1 TO A:H(B+D)=H(B+D)-G(D)*H(B):NEXT D
60 NEXT B:E=A
70 E=E-1:IF E<0;FOR B=0 TO A:PRINT A-B;G(B)/G:NEXT B:END
80 IF H(A+C-E)=0 THEN 70
90 FOR B=0 TO E:F=H(A+C):FOR D=0 TO E-B:H(A+C-D)=G(A+C-D)
100 NEXT D:FOR D=A+B+1 TO 0 STEP -1:G(D)=F(D)
110 NEXT D:NEXT B:C=A:A=E:GOTO 30

Размер: 298, H(m+n)

Пример: P₁(x)=2x³-3x+45; P₂(x)=3x³+10x²-8x-33.

3.4. Интегрирование и дифференцирование

Программа 29.

Первообразная многочлена:

где новые коэффициенты a_i=a_i-1/i, i=1...n+1
C - произвольный свободный член.

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

Производная от многочлена:

где новые коэффициенты a_i= ia_i+1, i=0...n-1

Управляющие ключи программы:
I - интегрировать;
D - дифференцировать;
P - показать результат;
N - новый многочлен;
T - закончить.

10 INPUT "n",A:FOR B=A TO 0 STEP -1:PRINT B;:INPUT C(B):NEXT B
20 INPUT "Операция",$:IF $="T";END
30 IF $="D";A=A-1:FOR B=0 TO A:C(B)=(B+1)*D(B):NEXT B
40 IF $="P";FOR B=A TO 0 STEP -1:PRINT B;" ";C(B):NEXT B
50 IF $="N" THEN 10
60 IF $¦"I" THEN 20
70 A=A+1:FOR B=A TO 1 STEP -1:C(B)=B(B)/B:NEXT B
80 INPUT "C",C:GOTO 20

Размер: 202, C(n+)

Пример: P(x)=9x²+8x+7;

3.5. Замена переменной

Программа 30. Линейная замена переменной.

Исходный многочлен: Q_n(y)=е_(i)q_iyⁱ, i=0...n

После замены y=ax+b:

Коэффициенты нового многочлена:

10 INPUT "a",A,"b",B,"n",C:FOR D=0 TO C:PRINT D;:INPUT H(D)
20 NEXT D:FOR D=0 TO C:F=0:G=1:FOR E=D TO C:F=F+G*H(E)
30 G=G*B*(E+1)/(E+1-D):NEXT E:PRINT D;F*A-D:NEXT D

Размер: 113, H(n)

Пример: y=2x+3; Q(y)=5+6y+7y²+8y³+9y⁴.

3.6. Разложение на сомножители

Квадратное уравнение:

a₂x²+a₁x+a₀=0.

Корни:

Вычисления в режиме калькулятора:

Пример 1: 25x²+12x+31=0.

Пример 2: 25x²+112x+31=0.

Программа 31. Кубическое уравнение.

Действительный корень выделяется методом дихотомии, после чего аналитически решается оставшееся квадратное уравнение. Область поиска корней определяется из неравенства: |x_i|<max_(i){a_i/a₃}+1

10 F=1:FOR E=0 TO 3:PRINT 3-E;:INPUT A(E)
20 IF E>0;A(E)=A(E)/A:IF ABS A(E)+1>F;F=ABS A(E)+1
30 NEXT E:A=0
40 E=A+B:G=E*A+C:IF G*A+D<0;A=A+F
50 F=F/2:A=A-F:IF A+F¦A THEN 40
60 E=-E/2:G=E*E-G:PRINT A:IF G>0 THEN 80
70 PRINT "Re";E,"Im";SQR -G:GOTO 10
80 PRINT SQR G-E,SQR G+E:GOTO 10

Размер: 197, G

Пример: 100x³+99,99x²+999999,99x-100=0.

Программа 32. Метод Хичкока. Алгебраическое уравнение степени n:

Уравнение решается численно, путем последовательного выделения квадратных трехчленов. Коэффициенты b₁ и b₀ квадратного трехчлена x²+b₁x+b₀ хранятся в ячейках C и D. Время сходимости процедуры зависит от того, насколько удачны начальные значения b₁ и b₀. В отдельных случаях сходимость медленная.

10 INPUT "n",A:FOR B=0 TO A:PRINT A-B;:INPUT J(B):NEXT B
20 D=1:E=1:C=K/J:IF A=1;PRINT -C:END
30 F=C*C/4-L/J:IF A=2 THEN 90
40 B=D:C=E:D=0:G=J:H=J:I=K-C*J:FOR E=3 TO A:F=I:I=I(E)-C*F-B*G
50 G=F:F=H:H=G-C*F-B*D:D=F:NEXT E:G=J(A)-B*G:E=H+C*F
60 D=F*F*B+E*H:E=C+(I*E-G*F)/D:D=B+(I*F*B+G*H)/D
70 IF ABS (B-D)+ABS (C-E)>(ABS D+ABS E)*1E^-10 THEN 40
80 FOR I=0 TO A-3:K(I)=K(I)-E*J(I)-D*I(I):NEXT I:F=E*E/4-D
90 G=-C/2:H=SQR ABS F:IF F>0;PRINT G-H,G+H:GOTO 110
100 PRINT "Re";G,"Im";H
110 A=A-2:IF A>0 THEN 20

Размер: 380, J(n).

Пример: x⁸-1=0.