Приближение Лагранжа -C++
Я обновил код. То, что я пытаюсь сделать, - это сохранить значения коэффициентов каждого лагранжа в указателе d (например, для L1(x) d[0] будет "x-x2 / x1-x2", d 1 будет (x-x2/x1-x2)*(x-x3/x1-x3) и т. д.
Моя проблема
1) как инициализировать d (я сделал d[0]=(zx[i])/(x[k]-x[i]), но я думаю, что это не правильно, "d [0]"
2) как инициализировать L_coeff. (Я использую L_coeff=new double[0], но я не уверен, что это правильно.
Упражнение таково: найти полиномиальное приближение Лагранжа для y(x)=cos(π x), x ∈−1,1, используя 5 точек (x = -1, -0,5, 0, 0,5 и 1).
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const double pi=3.14159265358979323846264338327950288;
// my function
double f(double x){
return (cos(pi*x));
}
//function to compute lagrange polynomial
double lagrange_polynomial(int N,double *x){
//N = degree of polynomial
double z,y;
double *L_coeff=new double [0];//L_coefficients of every Lagrange L_coefficient
double *d;//hold the polynomials values for every Lagrange coefficient
int k,i;
//computations for finding lagrange polynomial
//double sum=0;
for (k=0;k<N+1;k++){
for ( i=0;i<N+1;i++){
if (i==0) continue;
d[0]=(z-x[i])/(x[k]-x[i]);//initialization
if (i==k) L_coeff[k]=1.0;
else if (i!=k){
L_coeff[k]*=d[i];
}
}
cout <<"\nL("<<k<<") = "<<d[i]<<"\t\t\tf(x)= "<<f(x[k])<<endl;
}
}
int main()
{
double deg,result;
double *x;
cout <<"Give the degree of the polynomial :"<<endl;
cin >>deg;
for (int i=0;i<deg+1;i++){
cout <<"\nGive the points of interpolation : "<<endl;
cin >> x[i];
}
cout <<"\nThe Lagrange L_coefficients are: "<<endl;
result=lagrange_polynomial(deg,x);
return 0;
}
3 ответа
Поскольку это, кажется, домашнее задание, я не собираюсь давать вам исчерпывающий ответ, а скорее попытаюсь направить вас в нужное русло.
- Как вы представляете многочлены в компьютерном программном обеспечении? Интуитивно понятная версия, которую вы хотите заархивировать как символическое выражение, такое как 3x^3+5x^2-4, очень непрактична для дальнейших вычислений.
- Полином полностью определяется путем сохранения (и вывода) его коэффициентов.
То, что вы делаете выше, надеется, что C++ сделает некоторые алгебраические манипуляции для вас и упростит ваш продукт с помощью символической переменной. Это ничего не может сделать C++ без особых усилий.
У вас есть два варианта:
- Либо используйте правильную систему компьютерной алгебры, которая может выполнять символические манипуляции (например, Maple или Mathematica)
- Если вы связаны с C++, вам нужно немного подумать, как можно вычислить отдельные коэффициенты полинома. Выходные данные вашей программы могут быть только списком чисел (который вы, конечно, можете форматировать как красивую строку в соответствии с символическим выражением).
Надеюсь, что это дает вам некоторые идеи, как начать.
Редактировать 1
В вашем коде все еще есть неопределенное выражение, так как вы никогда не устанавливаете значение в y
, Это оставляет prod*=(y-x[i])/(x[k]-x[i])
как выражение, которое не будет возвращать значимые данные. C++ может работать только с числами, и y
для тебя сейчас нет числа, но ты считаешь его символом.
Вы можете оценить приближение Лагранжа, скажем, значение 1
, если бы вы установили y=1
в вашем коде. Это даст вам (насколько я вижу сейчас) правильное значение функции, но не будет описания самой функции.
Может быть, вы должны сначала взять ручку и лист бумаги и попытаться записать выражение как точную математику. Попробуйте получить реальное представление о том, что вы хотите вычислить. Если вы сделали это, возможно, вы вернетесь сюда и расскажете нам свои мысли. Это должно помочь вам понять, что там происходит.
И всегда помните: C++ нужны цифры, а не символы. Всякий раз, когда в выражении на вашем листе бумаги есть символ, о котором вы не знаете значения, вы можете либо найти способ вычисления значения из известных значений, либо вы должны исключить необходимость вычисления с использованием этого символа.
PS: не считается хорошим стилем публиковать одинаковые вопросы на нескольких форумах одновременно...
Редактировать 2
Теперь вы оцениваете функцию в точке y=0.3. Это путь, если вы хотите оценить полином. Однако, как вы заявили, вы хотите, чтобы все коэффициенты полинома.
Опять же, я все еще чувствую, что вы не поняли математику проблемы. Может быть, я приведу небольшой пример. Я собираюсь использовать обозначение, как оно используется в статье в Википедии.
Предположим, у нас было k=2 и x=-1, 1. Кроме того, позвольте мне просто назвать вашу cos-функцию f для простоты. (Обозначения станут довольно безобразными без латекса...) Тогда полином Лагранжа определяется как
f(x_0) * l_0(x) + f(x_1)*l_1(x)
где (выполняя упрощения снова символически)
l_0(x)= (x - x_1)/(x_0 - x_1) = -1/2 * (x-1) = -1/2 *x + 1/2
l_1(x)= (x - x_0)/(x_1 - x_0) = 1/2 * (x+1) = 1/2 * x + 1/2
Итак, вы лагранжев полином
f(x_0) * (-1/2 *x + 1/2) + f(x_1) * 1/2 * x + 1/2
= 1/2 * (f(x_1) - f(x_0)) * x + 1/2 * (f(x_0) + f(x_1))
Итак, коэффициенты, которые вы хотите вычислить, будут 1/2 * (f(x_1) - f(x_0)) и 1/2 * (f(x_0) + f(x_1)).
Теперь ваша задача - найти алгоритм, который делает упрощение, которое я сделал, но без использования символов. Если вы знаете, как вычислить коэффициенты l_j, вы в основном сделали это, поскольку вы можете просто сложить коэффициенты, умноженные на соответствующее значение f.
Таким образом, в еще большей степени, вы должны найти способ умножать коэффициенты в l_j друг на друга по компонентам. Выясните, как это делается, и вы почти закончили.
Редактировать 3
Хорошо, давайте станем немного менее расплывчатыми.
Сначала мы хотим вычислить L_i(x). Это просто продукты линейных функций. Как сказано выше, мы должны представлять каждый многочлен как массив коэффициентов. Для хорошего стиля я буду использовать std::vector
вместо этого массива. Затем мы могли бы определить структуру данных, содержащую коэффициенты L_1(x), следующим образом:
std::vector L1 = std::vector(5);
// Lets assume our polynomial would then have the form
// L1[0] + L2[1]*x^1 + L2[2]*x^2 + L2[3]*x^3 + L2[4]*x^4
Теперь мы хотим заполнить этот многочлен значениями.
// First we have start with the polynomial 1 (which is of degree 0)
// Therefore set L1 accordingly:
L1[0] = 1;
L1[1] = 0; L1[2] = 0; L1[3] = 0; L1[4] = 0;
// Of course you could do this more elegant (using std::vectors constructor, for example)
for (int i = 0; i < N+1; ++i) {
if (i==0) continue; /// For i=0, there will be no polynomial multiplication
// Otherwise, we have to multiply L1 with the polynomial
// (x - x[i]) / (x[0] - x[i])
// First, note that (x[0] - x[i]) ist just a scalar; we will save it:
double c = (x[0] - x[i]);
// Now we multiply L_1 first with (x-x[1]). How does this multiplication change our
// coefficients? Easy enough: The coefficient of x^1 for example is just
// L1[0] - L1[1] * x[1]. Other coefficients are done similary. Futhermore, we have
// to divide by c, which leaves our coefficient as
// (L1[0] - L1[1] * x[1])/c. Let's apply this to the vector:
L1[4] = (L1[3] - L1[4] * x[1])/c;
L1[3] = (L1[2] - L1[3] * x[1])/c;
L1[2] = (L1[1] - L1[2] * x[1])/c;
L1[1] = (L1[0] - L1[1] * x[1])/c;
L1[0] = ( - L1[0] * x[1])/c;
// There we are, polynomial updated.
}
Это, конечно, должно быть сделано для всех L_i. Затем L_i нужно добавить и умножить на функцию. Это для вас, чтобы выяснить. (Обратите внимание, что я сделал много неэффективных вещей там, но я надеюсь, что это поможет вам лучше понять детали.)
Надеюсь, это даст вам некоторое представление о том, как вы могли бы продолжить.
Переменная y
на самом деле не переменная в вашем коде, но представляет переменную P(y)
вашего приближения Лагранжа.
Таким образом, вы должны понимать расчеты prod*=(y-x[i])/(x[k]-x[i])
а также sum+=prod*f
не прямо, а символически.
Вы можете обойти это, определив свое приближение по серии
c[0] * y^0 + c[1] * y^1 + ...
представлен массивом c[]
в коде. Тогда вы можете, например, реализовать умножение
d = c * (y-x[i])/(x[k]-x[i])
как коэффициент
d[i] = -c[i]*x[i]/(x[k]-x[i]) + c[i-1]/(x[k]-x[i])
Таким же образом вы должны реализовать сложение и присваивания на основе компонентов.
Тогда результатом всегда будут коэффициенты представления вашей серии в переменной y
,
Просто несколько комментариев в дополнение к существующим ответам.
Упражнение: Найти полиномиальное приближение Лагранжа для y(x)=cos(π x), x ∈ [-1,1], используя 5 точек (x = -1, -0.5, 0, 0.5 и 1).
Первое, что ваш main()
делает, это спросить степень многочлена. Вы не должны делать это. Степень полинома полностью определяется количеством контрольных точек. В этом случае вы должны построить уникальный многочлен Лагранжа четвертого порядка, который проходит через пять точек (x i, cos (π x i)), где значения x i - это те пять указанных точек.
const double pi=3.1415;
Это значение не годится для поплавка, не говоря уже о двойном. Вы должны использовать что-то вроде const double pi=3.14159265358979323846264338327950288;
Или еще лучше, не используйте pi
совсем. Вы должны точно знать, какие значения y соответствуют данным значениям x. Что такое cos(-π), cos(-π/2), cos(0), cos(π/2) и cos(π)?