Задачка на многочлен Чебышева

Дано целое n от 2 к 20 и действительное Е > 0. Найти с точностью Е все корни n-ого многочлена Чебышева T[n](x) , который определяется формулами T₀(x)=1, T₁(x)=x, T_k(x)=2*x*T_k-1(x)-T_k-2(x),
(k=2,3,....).

Кто может помочь?

Сообщение отредактировано: Romtek - 29.06.05, 17:02

Цитата SashA @ 29.06.05, 14:57

Кто может помочь?

В чем? По значению X0 и X1 с помощью рекуррентной формулы найти X2, ... ? Числа Фибоначчи знаешь как находятся? Здесь тот же принцип...

Нет, не все так просто, как показалось...
Вот что у меня получилось: сначала ищем полином Чебышева N-ой степени, а потом придется решать его (я бы решал методом Штурма). Вот так находится полином:

uses crt;
 
const
  maxOrder = 20;
type
  coeffType = array[0 .. maxOrder] of integer;
 
{ Это только для контроля результатов }
procedure print_coeffs(var coeffs: coeffType);
const
  sign: array[boolean] of string[3] =
    (' - ', ' + ');
var
  before: boolean;
  i: integer;
begin
  before := false;
  for i := maxOrder downto 0 do begin
    if coeffs[i] <> 0 then begin
      if before then write(sign[coeffs[i] > 0])
      else before := true;
      write('x^', i, '*', abs(coeffs[i]));
    end;
  end;
end;
 
{ Дополнительные процедуры }
procedure mult_2x(var res: coeffType;
          const cf: coeffType);
var i: integer;
begin
  move(cf[0], res[1], pred(maxOrder)*sizeof(integer));
  res[0] := 0;
  for i := 0 to maxOrder do res[i] := res[i]*2;
end;
procedure minus(var From: coeffType;
          const What: coeffType);
var i: integer;
begin
  for i := 0 to maxOrder do
    from[i] := from[i] - what[i];
end;
 
{ Процедура, находящая коэффициенты полинома Чебышева степени N }
procedure get_poly(var coeffs: coeffType; n: integer);
var
  i: integer;
  cf_zero, cf_one, cf_curr: coeffType;
begin
  fillchar(cf_curr, sizeof(coeffType), 0);
  fillchar(cf_zero, sizeof(coeffType), 0);
  fillchar(cf_one, sizeof(coeffType), 0);
 
  cf_zero[0] := 1; cf_one[1] := 1;
 
  for i := 2 to n do begin
    mult_2x(cf_curr, cf_one);
    minus(cf_curr, cf_zero);
 
    cf_zero := cf_one;
    cf_one := cf_curr;
  end;
  coeffs := cf_curr;
end;
 
var
  coeffs: coeffType;
 
begin
  clrscr;
  get_poly(coeffs, 2);
 
  { это - только для проверки }
  print_coeffs(coeffs);
 
  { Здесь - решай уравнение, заданное коэффициентами }
end.

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

Значит так. Имеем полином Чебышева, заданный уравнением
T₀(x)=1, T₁(x)=x, T_k(x)=2*x*T_k-1(x)-T_k-2(x), (k=2,3,....).

Распишем здесь для пояснения полиномы до 4-го порядка включительно:
T₀(x)=1
T₁(x)=x
T₂(x)=2x² - 1
T₃(x)=4x³ - 3x
T₄(x)=8x⁴ - 8x² + 1

Теперь выпишем коэффициенты этих полиномов, сохраняя порядок полинома от меньшей степени к наибольшей:

 1
 0  1
-1  0  2
 0 -3  0  4
 1  0 -8  0  8

Type
  Coeff = array [0..20] of integer; { Массива тех самых коэффициентов }
  T = array [0..20] of Coeff; { Массив от массива коэффициентов. Иными словами, матрица [0..21,0..21] }

Таким образом, массив коэффициентов Coeff будут заполняться в том же порядке.
Можно представить будущую структуру заполнения массива так:

 T [0] = (1, 0, 0, 0, ....);
 T [1] = (0, 1, 0, 0, ....);
 T [2] = (-1, 0, 2, 0, ....);
 T [3] = (0, -3, 0, 4, 0, ....);
 T [4] = (1, 0, -8, 0, 8, 0,...);

Но это нам ещё предстоит сделать дальше.

Теперь возьмём, к примеру, полином 3-го порядка. В какой последовательности мы находим его коэффициенты?
Обозначим за Polinom_0 известные нам коэффициенты (1, 0, 0, ...)
и за Polinom_1 (0, 1, 0, 0, ...).
Как нам найти коэффициенты Polinom_2 ? Конечно же, по заданной рекуррентной формуле!
Она гласит: T₂(x)=2x*T₁(x) - T₀(x) ,
или Polinom_2 = 2x*Polinom_1 - Polinom_0.

Сейчас надо превратить это выражение в разность двух массивов коэффициентов, чтобы мы смогли найти Polinom_2.
Рассмотрим стадию "превращения":
Получение коэффициентов x*Polinom_1 достигается сдвигом коэффициентов Polinom_1 вправо на одну клетку (повышение порядка полинома). Т.е. x*Polinom_1 = (0, 0, 1, 0, 0, ...)
Умножение выглядит совсем просто: надо умножить все ячейки массива на 2.
Polinom_2 = 2*x*Polinom_1 = (0, 0, 2, 0, 0, ...)

Теперь вычтем из коэффициентов полученного Polinom_2 полином Polinom_1:
(0, 0, 2, 0, 0, ...)
-
(1, 0, 0, 0, 0, ...)
-------------------
(-1, 0, 2, 0, 0, ...)

Получили массив коэффициентов T[2]. То есть полином 2-го порядка выглядит так:
T₂(x)=2x*T₁(x) - T₀(x).
Для полиномов следующих порядков аналогичные действия.

Накатал я здесь немало и наверно запугал "многочисленными" операциями. На самом деле их здесь почти нет.
Удачи!

Цитата

{ Здесь - решай уравнение, заданное коэффициентами }

Напишите пожалуйста подробнее, никак понять не могу.

в,
выше мы с Romtek-ом объяснили, что нужно сделать для того, чтобы найти коэффициенты многочлена Чебышева... Но это еще не все, теперь его еще нужно решить, ведь по условию надо

Цитата SashA @ 29.06.05, 14:57

Найти с точностью Е все корни n-ого многочлена Чебышева

Допустим, было задано N, и ты получил полином T_N(x)=... Осталось его решить. Для этого тебе нужно выбрать метод, с помощью которого можно вычислить корни полинома до 20-ой степени.

Вот тут: FAQ: Численное решение уравнений итерационными методами есть то, что нужно для нахождения корней многочлена...

Как это можно сделать методом последовательных приближени? Никак немогу решить полином.

Цитата в @ 01.07.05, 09:21

Как это можно сделать методом последовательных приближени? Никак немогу решить полином.

Что именно не получается?? Мы ж не телепаты... ((
Скорее всего у тебя проблема с начальным приближением.... Расширь границы поиска...