Mixing
Polynomial curve fitting in linear algebra. Why do you need a polynomial of n-1?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I am reading this text:
and I'm confused at this part:
If all x-coordinates of the points are distinct, then there is precisely one polynomial function of degree n - 1 (or less) that fits the n points, as shown in Figure 1.4.
Why is this? So I can see that if there were 2 points, there could be a polynomial of degree 1 (say something like 2x) that could fit the two distinct points. Additionally, if there are 3 points, you'd need a parabola or something to fit the 3 distinct points. But where is the rule from? I'm rereading my old precalc textbook and I can't find anything of the sort.
Lastly, how did the text get this:
a0 = 24, a1 = -28, and a2 = 8
linear-algebra
asked Jul 16 at 14:39
Jwan622
1,61211224
add a comment |Â
up vote
2
down vote
favorite
I am reading this text:
and I'm confused at this part:
If all x-coordinates of the points are distinct, then there is precisely one polynomial function of degree n - 1 (or less) that fits the n points, as shown in Figure 1.4.
Why is this? So I can see that if there were 2 points, there could be a polynomial of degree 1 (say something like 2x) that could fit the two distinct points. Additionally, if there are 3 points, you'd need a parabola or something to fit the 3 distinct points. But where is the rule from? I'm rereading my old precalc textbook and I can't find anything of the sort.
Lastly, how did the text get this:
a0 = 24, a1 = -28, and a2 = 8
linear-algebra
asked Jul 16 at 14:39
Jwan622
1,61211224
Count the number of the polynomial coefficients.
– gammatester
Jul 16 at 14:40
It comes from phrasing the problem as a linear algebra problem by encoding the coefficients of the polynomial $sum a_i x^i$ as a vector $(a_1,dots,a_n-1)$. The uniqueness will be because the matrix get will be invertible
– Calvin Khor
Jul 16 at 14:41
A polynomial of degree $n-1$ has $n$ coefficients, simply. To get them, you write a linear system of $n$ equations in $n$ unknowns, and it is no big deal to show that the system is not degenerate.
– Yves Daoust
Jul 16 at 14:53
@Jwan622 Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here meta.stackexchange.com/questions/5234/…
– gimusi
Aug 8 at 23:04
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am reading this text:
and I'm confused at this part:
If all x-coordinates of the points are distinct, then there is precisely one polynomial function of degree n - 1 (or less) that fits the n points, as shown in Figure 1.4.
Why is this? So I can see that if there were 2 points, there could be a polynomial of degree 1 (say something like 2x) that could fit the two distinct points. Additionally, if there are 3 points, you'd need a parabola or something to fit the 3 distinct points. But where is the rule from? I'm rereading my old precalc textbook and I can't find anything of the sort.
Lastly, how did the text get this:
a0 = 24, a1 = -28, and a2 = 8
linear-algebra
asked Jul 16 at 14:39
Jwan622
1,61211224
I am reading this text:
and I'm confused at this part:
If all x-coordinates of the points are distinct, then there is precisely one polynomial function of degree n - 1 (or less) that fits the n points, as shown in Figure 1.4.
Why is this? So I can see that if there were 2 points, there could be a polynomial of degree 1 (say something like 2x) that could fit the two distinct points. Additionally, if there are 3 points, you'd need a parabola or something to fit the 3 distinct points. But where is the rule from? I'm rereading my old precalc textbook and I can't find anything of the sort.
Lastly, how did the text get this:
a0 = 24, a1 = -28, and a2 = 8
linear-algebra
asked Jul 16 at 14:39
Jwan622
1,61211224
asked Jul 16 at 14:39
Jwan622
1,61211224
asked Jul 16 at 14:39
Jwan622
1,61211224
asked Jul 16 at 14:39
Jwan622
1,61211224
1,61211224
Count the number of the polynomial coefficients.
– gammatester
Jul 16 at 14:40
It comes from phrasing the problem as a linear algebra problem by encoding the coefficients of the polynomial $sum a_i x^i$ as a vector $(a_1,dots,a_n-1)$. The uniqueness will be because the matrix get will be invertible
– Calvin Khor
Jul 16 at 14:41
A polynomial of degree $n-1$ has $n$ coefficients, simply. To get them, you write a linear system of $n$ equations in $n$ unknowns, and it is no big deal to show that the system is not degenerate.
– Yves Daoust
Jul 16 at 14:53
@Jwan622 Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here meta.stackexchange.com/questions/5234/…
– gimusi
Aug 8 at 23:04
add a comment |Â
Count the number of the polynomial coefficients.
– gammatester
Jul 16 at 14:40
It comes from phrasing the problem as a linear algebra problem by encoding the coefficients of the polynomial $sum a_i x^i$ as a vector $(a_1,dots,a_n-1)$. The uniqueness will be because the matrix get will be invertible
– Calvin Khor
Jul 16 at 14:41
A polynomial of degree $n-1$ has $n$ coefficients, simply. To get them, you write a linear system of $n$ equations in $n$ unknowns, and it is no big deal to show that the system is not degenerate.
– Yves Daoust
Jul 16 at 14:53
@Jwan622 Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here meta.stackexchange.com/questions/5234/…
– gimusi
Aug 8 at 23:04
Count the number of the polynomial coefficients.
– gammatester
Jul 16 at 14:40
Count the number of the polynomial coefficients.
– gammatester
Jul 16 at 14:40
It comes from phrasing the problem as a linear algebra problem by encoding the coefficients of the polynomial $sum a_i x^i$ as a vector $(a_1,dots,a_n-1)$. The uniqueness will be because the matrix get will be invertible
– Calvin Khor
Jul 16 at 14:41
It comes from phrasing the problem as a linear algebra problem by encoding the coefficients of the polynomial $sum a_i x^i$ as a vector $(a_1,dots,a_n-1)$. The uniqueness will be because the matrix get will be invertible
– Calvin Khor
Jul 16 at 14:41
A polynomial of degree $n-1$ has $n$ coefficients, simply. To get them, you write a linear system of $n$ equations in $n$ unknowns, and it is no big deal to show that the system is not degenerate.
– Yves Daoust
Jul 16 at 14:53
A polynomial of degree $n-1$ has $n$ coefficients, simply. To get them, you write a linear system of $n$ equations in $n$ unknowns, and it is no big deal to show that the system is not degenerate.
– Yves Daoust
Jul 16 at 14:53
@Jwan622 Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here meta.stackexchange.com/questions/5234/…
– gimusi
Aug 8 at 23:04
@Jwan622 Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here meta.stackexchange.com/questions/5234/…
– gimusi
Aug 8 at 23:04
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Simply note that the general polynomial function of degree $n$ is defined by $n+1$ coefficients $a_0,a_1,ldots,a_n$
$$p_n(x)=a_nx^n+a_n-1x^n-1+ldots+a_1x+a_0$$
and thus we need exactly $n+1$ (independent) conditions to obtain a linear system with an unique solution.
answered Jul 16 at 14:42
gimusi
65.4k73684
add a comment |Â
up vote
2
down vote
Given $x_0 < dots < x_n-1$ and values $y=(y_0 , dots, y_n-1)$, finding a polynomial $sum_i=0^n-1 a_i x^i$ of degree $n-1$ such that
$p(x_i) = y_i$ for every $i$ is equivalent to solving for $a=(a_0,dots,a_n-1)$ in the matrix equation $Va = y$,
$$ beginpmatrix
x_0^0 & x_0^1& dots& x_0^n-1 \
x_1^0 & x_1^1& dots& x_1^n-1 \
vdots & vdots & & vdots \
x_n-1^0 & x_n-1^1& dots& x_n-1^n-1 \endpmatrix beginpmatrixa_0\a_1\vdots\ a_n-1endpmatrix = beginpmatrixy_0\y_1\vdots\ y_n-1endpmatrix.$$
Indeed, this is what is next written("to solve for the $n$ coefficients...") in your text, but in the form of $n$ equations.
You may notice that this matrix $V$ is the so-called Vandermonde matrix which is invertible iff the given $x$ coordinates are all different.
Lastly, how did the text get...
In the given example, you have $(x_0,x_1,x_2) = (1,2,3)$ and you are trying to match with the values $(y_0,y_1,y_2)=(4,0,12)$. So just plug these values in and you should see that (assuming there is no typo in your book)
$$beginpmatrixa_0\a_1\a_2endpmatrix = beginpmatrix1 & 1 & 1\ 1 &2 &4\ 1&3&9 endpmatrix^-1beginpmatrix 4\0\12endpmatrix = beginpmatrix 24\-28\8endpmatrix.$$
If you were unsure about the uniqueness part: the above exhibits one solution to the problem and the solution is unique since the existence of two different solutions $$a=(a_0,dots,a_n-1),quad b=(b_0,dots,b_n-1)$$ would imply (since $V(b-a) =0$) that the kernel of the Vandermonde matrix $V$ has dimension $geq 1$. Indeed, for any matrix $M$, any two solutions $a,a'$ to $Ma=y$ must be related via $a=a'+k$ for some $kinker M$. In particular if you use a higher degree polynomial(= adding columns to $V$), you will have infinitely many solutions.
If you were wondering if you can use a lower degree polynomial: not in general. This corresponds to removing columns from $V$ to obtain a nonsquare matrix $V'$, which is of lower rank. In particular the Rank-Nullity theorem tells us that the image is not all of $mathbb R^n$, and picking any $(y_0,dots y_n-1)$ in $mathbb R^n setminus operatornameIm(V') neq emptyset$ provides a counterexample.
answered Jul 16 at 14:49
Calvin Khor
8,15911133
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Simply note that the general polynomial function of degree $n$ is defined by $n+1$ coefficients $a_0,a_1,ldots,a_n$
$$p_n(x)=a_nx^n+a_n-1x^n-1+ldots+a_1x+a_0$$
and thus we need exactly $n+1$ (independent) conditions to obtain a linear system with an unique solution.
answered Jul 16 at 14:42
gimusi
65.4k73684
add a comment |Â
up vote
1
down vote
accepted
Simply note that the general polynomial function of degree $n$ is defined by $n+1$ coefficients $a_0,a_1,ldots,a_n$
$$p_n(x)=a_nx^n+a_n-1x^n-1+ldots+a_1x+a_0$$
and thus we need exactly $n+1$ (independent) conditions to obtain a linear system with an unique solution.
answered Jul 16 at 14:42
gimusi
65.4k73684
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Simply note that the general polynomial function of degree $n$ is defined by $n+1$ coefficients $a_0,a_1,ldots,a_n$
$$p_n(x)=a_nx^n+a_n-1x^n-1+ldots+a_1x+a_0$$
and thus we need exactly $n+1$ (independent) conditions to obtain a linear system with an unique solution.
answered Jul 16 at 14:42
gimusi
65.4k73684
Simply note that the general polynomial function of degree $n$ is defined by $n+1$ coefficients $a_0,a_1,ldots,a_n$
$$p_n(x)=a_nx^n+a_n-1x^n-1+ldots+a_1x+a_0$$
and thus we need exactly $n+1$ (independent) conditions to obtain a linear system with an unique solution.
answered Jul 16 at 14:42
gimusi
65.4k73684
answered Jul 16 at 14:42
gimusi
65.4k73684
answered Jul 16 at 14:42
gimusi
65.4k73684
answered Jul 16 at 14:42
gimusi
65.4k73684
65.4k73684
add a comment |Â
add a comment |Â
up vote
2
down vote
Given $x_0 < dots < x_n-1$ and values $y=(y_0 , dots, y_n-1)$, finding a polynomial $sum_i=0^n-1 a_i x^i$ of degree $n-1$ such that
$p(x_i) = y_i$ for every $i$ is equivalent to solving for $a=(a_0,dots,a_n-1)$ in the matrix equation $Va = y$,
$$ beginpmatrix
x_0^0 & x_0^1& dots& x_0^n-1 \
x_1^0 & x_1^1& dots& x_1^n-1 \
vdots & vdots & & vdots \
x_n-1^0 & x_n-1^1& dots& x_n-1^n-1 \endpmatrix beginpmatrixa_0\a_1\vdots\ a_n-1endpmatrix = beginpmatrixy_0\y_1\vdots\ y_n-1endpmatrix.$$
Indeed, this is what is next written("to solve for the $n$ coefficients...") in your text, but in the form of $n$ equations.
You may notice that this matrix $V$ is the so-called Vandermonde matrix which is invertible iff the given $x$ coordinates are all different.
Lastly, how did the text get...
In the given example, you have $(x_0,x_1,x_2) = (1,2,3)$ and you are trying to match with the values $(y_0,y_1,y_2)=(4,0,12)$. So just plug these values in and you should see that (assuming there is no typo in your book)
$$beginpmatrixa_0\a_1\a_2endpmatrix = beginpmatrix1 & 1 & 1\ 1 &2 &4\ 1&3&9 endpmatrix^-1beginpmatrix 4\0\12endpmatrix = beginpmatrix 24\-28\8endpmatrix.$$
If you were unsure about the uniqueness part: the above exhibits one solution to the problem and the solution is unique since the existence of two different solutions $$a=(a_0,dots,a_n-1),quad b=(b_0,dots,b_n-1)$$ would imply (since $V(b-a) =0$) that the kernel of the Vandermonde matrix $V$ has dimension $geq 1$. Indeed, for any matrix $M$, any two solutions $a,a'$ to $Ma=y$ must be related via $a=a'+k$ for some $kinker M$. In particular if you use a higher degree polynomial(= adding columns to $V$), you will have infinitely many solutions.
If you were wondering if you can use a lower degree polynomial: not in general. This corresponds to removing columns from $V$ to obtain a nonsquare matrix $V'$, which is of lower rank. In particular the Rank-Nullity theorem tells us that the image is not all of $mathbb R^n$, and picking any $(y_0,dots y_n-1)$ in $mathbb R^n setminus operatornameIm(V') neq emptyset$ provides a counterexample.
answered Jul 16 at 14:49
Calvin Khor
8,15911133
add a comment |Â
up vote
2
down vote
Given $x_0 < dots < x_n-1$ and values $y=(y_0 , dots, y_n-1)$, finding a polynomial $sum_i=0^n-1 a_i x^i$ of degree $n-1$ such that
$p(x_i) = y_i$ for every $i$ is equivalent to solving for $a=(a_0,dots,a_n-1)$ in the matrix equation $Va = y$,
$$ beginpmatrix
x_0^0 & x_0^1& dots& x_0^n-1 \
x_1^0 & x_1^1& dots& x_1^n-1 \
vdots & vdots & & vdots \
x_n-1^0 & x_n-1^1& dots& x_n-1^n-1 \endpmatrix beginpmatrixa_0\a_1\vdots\ a_n-1endpmatrix = beginpmatrixy_0\y_1\vdots\ y_n-1endpmatrix.$$
Indeed, this is what is next written("to solve for the $n$ coefficients...") in your text, but in the form of $n$ equations.
You may notice that this matrix $V$ is the so-called Vandermonde matrix which is invertible iff the given $x$ coordinates are all different.
Lastly, how did the text get...
In the given example, you have $(x_0,x_1,x_2) = (1,2,3)$ and you are trying to match with the values $(y_0,y_1,y_2)=(4,0,12)$. So just plug these values in and you should see that (assuming there is no typo in your book)
$$beginpmatrixa_0\a_1\a_2endpmatrix = beginpmatrix1 & 1 & 1\ 1 &2 &4\ 1&3&9 endpmatrix^-1beginpmatrix 4\0\12endpmatrix = beginpmatrix 24\-28\8endpmatrix.$$
If you were unsure about the uniqueness part: the above exhibits one solution to the problem and the solution is unique since the existence of two different solutions $$a=(a_0,dots,a_n-1),quad b=(b_0,dots,b_n-1)$$ would imply (since $V(b-a) =0$) that the kernel of the Vandermonde matrix $V$ has dimension $geq 1$. Indeed, for any matrix $M$, any two solutions $a,a'$ to $Ma=y$ must be related via $a=a'+k$ for some $kinker M$. In particular if you use a higher degree polynomial(= adding columns to $V$), you will have infinitely many solutions.
If you were wondering if you can use a lower degree polynomial: not in general. This corresponds to removing columns from $V$ to obtain a nonsquare matrix $V'$, which is of lower rank. In particular the Rank-Nullity theorem tells us that the image is not all of $mathbb R^n$, and picking any $(y_0,dots y_n-1)$ in $mathbb R^n setminus operatornameIm(V') neq emptyset$ provides a counterexample.
answered Jul 16 at 14:49
Calvin Khor
8,15911133
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Given $x_0 < dots < x_n-1$ and values $y=(y_0 , dots, y_n-1)$, finding a polynomial $sum_i=0^n-1 a_i x^i$ of degree $n-1$ such that
$p(x_i) = y_i$ for every $i$ is equivalent to solving for $a=(a_0,dots,a_n-1)$ in the matrix equation $Va = y$,
$$ beginpmatrix
x_0^0 & x_0^1& dots& x_0^n-1 \
x_1^0 & x_1^1& dots& x_1^n-1 \
vdots & vdots & & vdots \
x_n-1^0 & x_n-1^1& dots& x_n-1^n-1 \endpmatrix beginpmatrixa_0\a_1\vdots\ a_n-1endpmatrix = beginpmatrixy_0\y_1\vdots\ y_n-1endpmatrix.$$
Indeed, this is what is next written("to solve for the $n$ coefficients...") in your text, but in the form of $n$ equations.
You may notice that this matrix $V$ is the so-called Vandermonde matrix which is invertible iff the given $x$ coordinates are all different.
Lastly, how did the text get...
In the given example, you have $(x_0,x_1,x_2) = (1,2,3)$ and you are trying to match with the values $(y_0,y_1,y_2)=(4,0,12)$. So just plug these values in and you should see that (assuming there is no typo in your book)
$$beginpmatrixa_0\a_1\a_2endpmatrix = beginpmatrix1 & 1 & 1\ 1 &2 &4\ 1&3&9 endpmatrix^-1beginpmatrix 4\0\12endpmatrix = beginpmatrix 24\-28\8endpmatrix.$$
If you were unsure about the uniqueness part: the above exhibits one solution to the problem and the solution is unique since the existence of two different solutions $$a=(a_0,dots,a_n-1),quad b=(b_0,dots,b_n-1)$$ would imply (since $V(b-a) =0$) that the kernel of the Vandermonde matrix $V$ has dimension $geq 1$. Indeed, for any matrix $M$, any two solutions $a,a'$ to $Ma=y$ must be related via $a=a'+k$ for some $kinker M$. In particular if you use a higher degree polynomial(= adding columns to $V$), you will have infinitely many solutions.
If you were wondering if you can use a lower degree polynomial: not in general. This corresponds to removing columns from $V$ to obtain a nonsquare matrix $V'$, which is of lower rank. In particular the Rank-Nullity theorem tells us that the image is not all of $mathbb R^n$, and picking any $(y_0,dots y_n-1)$ in $mathbb R^n setminus operatornameIm(V') neq emptyset$ provides a counterexample.
answered Jul 16 at 14:49
Calvin Khor
8,15911133
Given $x_0 < dots < x_n-1$ and values $y=(y_0 , dots, y_n-1)$, finding a polynomial $sum_i=0^n-1 a_i x^i$ of degree $n-1$ such that
$p(x_i) = y_i$ for every $i$ is equivalent to solving for $a=(a_0,dots,a_n-1)$ in the matrix equation $Va = y$,
$$ beginpmatrix
x_0^0 & x_0^1& dots& x_0^n-1 \
x_1^0 & x_1^1& dots& x_1^n-1 \
vdots & vdots & & vdots \
x_n-1^0 & x_n-1^1& dots& x_n-1^n-1 \endpmatrix beginpmatrixa_0\a_1\vdots\ a_n-1endpmatrix = beginpmatrixy_0\y_1\vdots\ y_n-1endpmatrix.$$
Indeed, this is what is next written("to solve for the $n$ coefficients...") in your text, but in the form of $n$ equations.
You may notice that this matrix $V$ is the so-called Vandermonde matrix which is invertible iff the given $x$ coordinates are all different.
Lastly, how did the text get...
In the given example, you have $(x_0,x_1,x_2) = (1,2,3)$ and you are trying to match with the values $(y_0,y_1,y_2)=(4,0,12)$. So just plug these values in and you should see that (assuming there is no typo in your book)
$$beginpmatrixa_0\a_1\a_2endpmatrix = beginpmatrix1 & 1 & 1\ 1 &2 &4\ 1&3&9 endpmatrix^-1beginpmatrix 4\0\12endpmatrix = beginpmatrix 24\-28\8endpmatrix.$$
If you were unsure about the uniqueness part: the above exhibits one solution to the problem and the solution is unique since the existence of two different solutions $$a=(a_0,dots,a_n-1),quad b=(b_0,dots,b_n-1)$$ would imply (since $V(b-a) =0$) that the kernel of the Vandermonde matrix $V$ has dimension $geq 1$. Indeed, for any matrix $M$, any two solutions $a,a'$ to $Ma=y$ must be related via $a=a'+k$ for some $kinker M$. In particular if you use a higher degree polynomial(= adding columns to $V$), you will have infinitely many solutions.
If you were wondering if you can use a lower degree polynomial: not in general. This corresponds to removing columns from $V$ to obtain a nonsquare matrix $V'$, which is of lower rank. In particular the Rank-Nullity theorem tells us that the image is not all of $mathbb R^n$, and picking any $(y_0,dots y_n-1)$ in $mathbb R^n setminus operatornameIm(V') neq emptyset$ provides a counterexample.
answered Jul 16 at 14:49
Calvin Khor
8,15911133
edited Jul 16 at 16:27
answered Jul 16 at 14:49
Calvin Khor
8,15911133
answered Jul 16 at 14:49
Calvin Khor
8,15911133
answered Jul 16 at 14:49
Calvin Khor
8,15911133
8,15911133
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853468%2fpolynomial-curve-fitting-in-linear-algebra-why-do-you-need-a-polynomial-of-n-1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Count the number of the polynomial coefficients.
– gammatester
Jul 16 at 14:40
It comes from phrasing the problem as a linear algebra problem by encoding the coefficients of the polynomial $sum a_i x^i$ as a vector $(a_1,dots,a_n-1)$. The uniqueness will be because the matrix get will be invertible
– Calvin Khor
Jul 16 at 14:41
A polynomial of degree $n-1$ has $n$ coefficients, simply. To get them, you write a linear system of $n$ equations in $n$ unknowns, and it is no big deal to show that the system is not degenerate.
– Yves Daoust
Jul 16 at 14:53
@Jwan622 Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here meta.stackexchange.com/questions/5234/…
– gimusi
Aug 8 at 23:04