Сложная задача, Полином 5 - го порядка , нахождение корней Опции

[-Student-]

здравствуйте !
вот задали задание , такой темы ещё не проходили поэтому прошу помощи у вас .

нужно написать программу которая ищет корни из полинома 5 - го порядка с комплексными коэффициентами задаваемыми пользователями.

полином (или попросту многочлен) представляет собой алгебраическую сумму " (a+bi)x^5 + (a+bi)x^4+ ... (a+bi)x^n-1"

(a+bi) - комплексный коэффициент с мнимой еденицей "i" , a и b нужно задавать самому и для каждого "х" они будут разные ... фактически при раскрытия скобок получается что нужно решить 2 полинома , мнимый и действительный.

n - степень полинома (в данном случае степень n=5)

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

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

[volvo]

Есть программа, реализующая твое задание с использованием алгоритма Лагерра, но поскольку она на С++ (есть также исходник на Фортране), то приводить ее здесь я не буду, если интересно - обращайся в приват, дам ссылку. Или подождешь немного, и я попробую ее перевести на Паскаль/Дельфи?

[diehard]

подожду , практику надо 14 здавать

[volvo]

Значит, смотри, что получилось...

В аттаче - основной модуль, весь проект аттачить не стал, потому что не знаю, какой версией Delphi ты пользуешься, у меня BDS 2007, на более ранних проект не откроется (собственно программа должна работать на любой версии, начиная с D7 - именно там, насколько я помню, ввели модуль VarCmplx для поддержки комплексных чисел).

Теперь о программе: она находит корни любых полиномов (автор оригинала утверждает, что работает до полиномов 40-й степени). Я тестировал на таком:

(2 + i)*z² - (7 + i)*z + (15 + 10i) = 0
Для этого в процедуре Test коэффициенты задаются:

  coeffs^[2] := VarComplexCreate(2.0, 1.0);
  coeffs^[1] := -1 * VarComplexCreate(7.0, 1.0);
  coeffs^[0] := VarComplexCreate(15.0, 10.0);

(именно в таком порядке, индекс коэффициента должен совпадать со степенью переменной, не наоборот), Я надеюсь, понятно, что также, как я "зашил" данные в программе, из можно и ввести?

В результате получил 2 корня, как и положено:

root # 1 = (2 - 3i)
root # 2 = (1 + 2i)

, что является правильным ответом... Искать примеры полиномов более высоких порядков с известными корнями не стал, но поскольку для второй степени программа работает, то логично предположить, что будет она работать и для более высоких степеней. Тестируй, если что не так - говори, на каких исходных данных ошибается, какие должны быть результаты, и что выводит. Если уже есть составленные тесты для этого задания - вообще прекрасно, проверяй... Время у тебя еще есть

Вот модуль:
 Unit1.pas ( 9.65 килобайт ) Кол-во скачиваний: 380

[diehard]

огромное спасибо за перевод программы , но она почему - то не хочет у меня выводить результаты ... поставил на форму button и memo , вроде всё должно было быть правильно , по событию button1click идёт функция test в которой на memo идёт вывод корней :

 for i := 0 to n_roots - 1 do begin
	  Form1.Memo1.Lines.Add(format('root #%2d = (%s)', [i + 1, string(roots^[i])]));

но memo остаётся пустым, думаю что дело в этой строчке ... потому что толком не понял как она работает , а именно вот это format('root #%2d = (%s)'

ещё бы хотел спросить как коэффициенты задавать в самой программе , не изменяя ничего в коде ... создать ещё массив и поле edit для ввода ?

работаю в Delphi 7, если не затруднит закиньте пожалуйста весь проект.

[volvo]

Во-первых, сразу вопрос: ты файлы проекта с D2007 на D7 что, вручную переписывать будешь? Нет обратной совместимости, это я могу открыть твой проект, а наоборот - увы - нельзя... Так что у меня обратное предложение: заархивируй свой проект (без EXE-шника, разумеется), и прикрепи его.. я проверю, выполняется ли он у меня... Вот если нет, тогда и посмотрю, в чем дело. А уж если выполняется - то придется тебе искать нормальную версию Дельфи.

Дальше:

думаю что дело в этой строчке

Ну, правильно... "Не понимаю, значит, неправильно"... Эта строчка просто напросто форматирует строку, чтобы не писать:

      Form1.Memo1.Lines.Add('root #' + IntToStr(i + 1) + ' = (' + string(roots^[i]) + ')');

, я выбрал более компактный вариант...

[diehard]

вот , щас почемуто стал выдавать ошибку "Invalid Variant Type" , хотя в коде ничего не менял ...

[volvo]

Вот результат работы твоего проекта под BDS:

щас почемуто стал выдавать ошибку "Invalid Variant Type"

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

    for j := degree - 1 downto 0 do begin // Horner's scheme.
      gamma := (z * gamma) + beta;
      beta  := (z * beta)  + alpha;
      alpha := (z * alpha) + a[j];
    end;

вот таким:

    for j := degree - 1 downto 0 do begin // Horner's scheme.
      gamma := ComplexAdd(ComplexMult(z, gamma), beta);
      beta  := ComplexAdd(ComplexMult(z, beta), alpha);
      alpha := ComplexAdd(ComplexMult(z, alpha), a[j]);
    end;

Размер программы вырастет в несколько раз...

Попробуй простейший пример:

uses VarCmplx;

procedure TForm1.Button1Click(Sender: TObject);
var A,B,C:Variant;
begin
  A:=VarComplexCreate;
  B:=VarComplexCreate;
  C:=VarComplexCreate;
  A.Real:=1;
  A.Imaginary:=1;
  B:=A;
  C:=A+B;
  Caption:=string©;
end;

Заголовок должен смениться на '2+2i'... Если это не отработало - все-таки придется тебе реализовывать комплексную арифметику вручную...

[diehard]

проделал вышенаписанную процедуру ... как вы и говорили заголовок изменился на "2+2i".

[volvo]

Так. Уже лучше. Теперь еще 2 вещи: во-первых, у тебя в том проекте, который ты приаттачил, не установлен обработчик OnFormCreate. То есть, сама процедура FormCreate присутствует, а вот в ObjectInspector-е в Event-ах для формы - пусто... Назначь соответствующему эвенту эту процедуру.

Второе - где именно возникает "Invalid Variant Type"? На какой строке?

[diehard]

Во вкладке Events , по событию OnCreate (вроде этот , других похожих нету) выставил обработчик FormCreate

а ошибка возникает уже в процессе обработки , т.е. запускаю программу , нажимаю на кнопку и вылетает сообщение об ошибке.

[volvo]

а ошибка возникает уже в процессе обработки

, понимаю, что в процессе обработки... Я и спрашиваю, при выполнении какой строки, она вылетает? Какая строка в исходнике подсвечивается при возникновении исключения? В крайнем случае (если D7 не дает диагностику, где именно выброшено исключение) ставь брекпойнт на первую строку процедуры Test, и запускай программу... Дошел до брекпойнта - переноси его на след. строку (с заходом во все процедуры)... И продвигайся так до тех пор, пока не возникнет исключение, так ты точно узнаешь, ГДЕ ИМЕННО оно возникает, тогда будем думать, что там не так...

[diehard]

в процедуре Test при тесте с брейкпоинтом не вылетало ошибок с "Invalid Variant Type" и всегда указывало на брейкпоинт вплоть до этой строчки :

	coeffs^[0] := VarComplexCreate(15.0, 1.0); 

после этой строчки начала вылетать ошибка "Invalid Variant Type" и указывать на :

procedure TForm1.Button1Click(Sender: TObject);
begin
  test(2);
end;

а именно на : end;

Сообщение отредактировано: volvo - 28.11.2009 11:37

[volvo]

Не понимаю я, что там у тебя происходит, и каким образом 2 значения инициализируются нормально, а при инициализации третьего вдруг вылетает исключение... Значит, бери, описывай свой тип

TComplex = record
  Re, Im: Double;
end;

, и для его реализуй все необходимые операции: ComplexAdd, ComplexSub, ComplexMult, ComplexDiv (причем последние 2 - не только для обоих операндов комплексного типа, но и для "один комплексное число, другой - вещественное"), ComplexConj, ComplexAbs, ComplexSqrt, ну, и все, что там еще понадобится... И заменяй перегруженные операторы на вызовы функций, как я показывал выше. Возможно, это решит проблему...

(скажу сразу, в оригинальной программе на С++ используется готовый complex<double> со всеми перегрузками, а не "самодельный" тип)

[diehard]

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

[volvo]

Начинать - вот так:

type
  TComplex = record
    Re, im: double;
  end;

function ComplexAdd(a, b: TComplex): TComplex;
begin
  result.re := a.re + b.re;
  result.im := a.im + b.im;
end;
function ComplexSub(a, b: TComplex): TComplex;
begin
  result.re := a.re - b.re;
  result.im := a.im - b.im;
end;

function ComplexMult(a, b: TComplex): TComplex; overload;
begin
  result.re := a.re * b.re - a.im * b.im;
  result.im := a.re * b.im + a.im * b.re;
end;
function ComplexMult(a: TComplex; f: Double): TComplex; overload;
begin
  result.re := a.re * f;
  result.im := a.im * f;
end;

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

[diehard]

ну с делением вроде так :

function ComplexDiv(a, b: TComplex): Tcomplex;overload;
begin
result.re := a.re / b.re;
result.im := a.im / b.im;
end;

function ComplexDiv(a: TComplex; f: Double): Tcomplex;overload;
begin 
result.re := a.re / f;
result.im := a.im / f;
end;

а как быть с возведением в степень , нахождения корня ... какие именно коэффициенты надо использовать в функции ?т.е. что ( a.re(im) или b.re(im)) возводить? или из чего брать корень... и что такое "норма" .

З.Ы. голова уже не шарит с этими полиномами , весь день проискал в инете и ничего похожего нету ... только с действительными коэффициентами.

Сообщение отредактировано: diehard - 12.07.2008 19:39

[volvo]

Вот это попробуй:
 Unit1.pas ( 13.7 килобайт ) Кол-во скачиваний: 382


Просто скопируй содержимое этого файла в ClipBoard, открой свой проект, и замени все содержимое старого Unit1.pas тем, что скопировано...

Видишь, насколько увеличился размер файла? Я уж не говорю о читабельности?


Добавлено через 1 мин.
P.S. Деление "комплексное на комплексное" у тебя реализовано неверно, кстати...

[diehard]

Огромное спасибо ! программа работает ... Спасибо что уделил большое внимание моей проблеме и выручил меня !

[volvo]

Погоди... Рано радуешься... В программе был найден баг: при задании полинома степени больше, чем 2 она вылетала... Немного поправил, теперь работает: корректно найдены корни уравнения
z³ - 6*z² + 21*z - 52 = 0

root # 1 = ( 4.00, 0.00)
root # 2 = ( 1.00, 3.46)
root # 3 = ( 1.00, -3.46)

, что и требовалось доказать. Правильные корни: 4, (1 + 2i*sqrt(3)) и (1 - 2i*sqrt(3))...

В аттаче - новая версия программы