- #1

- 274

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Treadstone 71
- Start date

- #1

- 274

- 0

- #2

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

- #3

- 274

- 0

Let me just post the question completely, in case I said something wrong:

"Let [tex]S={x_1,...,x_N}[/tex] be a collection of real numbers, and let [tex](y_1,...,y_N)[/tex] be a sequence of real numbers. Fix an integer [tex]k<N[/tex]. In general, there need not be a polynomial [tex]p[/tex] of degree [tex]\leq k[/tex] such that [tex]p(x_j)=y_j[/tex] for [tex]j=1,...,N[/tex]. The next best thing one might ask for is a polynomial [tex]p[/tex] of degree less than [tex]k[/tex] for which the quantity

[tex](p(x_1)-y_1)^2+...+(p(x_N)-y_N)^2[/tex]

is minimized. Describe an approach that would produce such a [tex]p[/tex]."

I'm not sure how any function is equivalent to a polynomial.

"Let [tex]S={x_1,...,x_N}[/tex] be a collection of real numbers, and let [tex](y_1,...,y_N)[/tex] be a sequence of real numbers. Fix an integer [tex]k<N[/tex]. In general, there need not be a polynomial [tex]p[/tex] of degree [tex]\leq k[/tex] such that [tex]p(x_j)=y_j[/tex] for [tex]j=1,...,N[/tex]. The next best thing one might ask for is a polynomial [tex]p[/tex] of degree less than [tex]k[/tex] for which the quantity

[tex](p(x_1)-y_1)^2+...+(p(x_N)-y_N)^2[/tex]

is minimized. Describe an approach that would produce such a [tex]p[/tex]."

I'm not sure how any function is equivalent to a polynomial.

Last edited:

- #4

- 274

- 0

Let [tex]P[/tex] be the space of polynomials of degree [tex]\leq k[/tex]. Let [tex]p\in P[/tex]. Define [tex]T:P\rightarrow \mathbb{R}^N[/tex] by [tex]T(p)=(p(x_1),...,p(x_N))[/tex] and then proceed to use the dot product on [tex]\mathbb{R}^N[/tex] and somehow minimize it?

- #5

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Not even f(x) := x² + 2x + 1?I'm not sure how any function is equivalent to a polynomial.

You know techniques for minimizing functions in several variables. (what are the variables?) Why are you defining an inner product? It might be useful, but I get the feeling you simplyand somehow minimize it?

- #6

- 274

- 0

Hurkyl said:Not even f(x) := x² + 2x + 1?

What about f(x)=ln(x)?

Hurkyl said:You know techniques for minimizing functions in several variables. (what are the variables?) Why are you defining an inner product? It might be useful, but I get the feeling you simplywantto use an inner product on this problem!

I

Last edited:

- #7

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

Firstly, you did not limit the degree of the approximation required.

It is trivial that given a finite set of points and a function on them to R, that it might be realized by *some* polynomial, and equally trivial that it cannot in general be done by polys less than some fixed degree (less than the number of points). But none of that you bothered to state in the question.

Given points (x_1,..x_n) I can trivially produce some polynomial f such that f(x_i)=log(x_i) as long as deg(f) is allowed to be arbitrary. If you don't see that you can get a line passing through any two points in the plane (quadratic through any 3 etc), then you missed out on something somewhere.

Of course, less than n and it is impossible (generically), but you did not state that at the start.

You're simply doing some minimization problem in your case, albeit probably a hard one.

It is trivial that given a finite set of points and a function on them to R, that it might be realized by *some* polynomial, and equally trivial that it cannot in general be done by polys less than some fixed degree (less than the number of points). But none of that you bothered to state in the question.

Given points (x_1,..x_n) I can trivially produce some polynomial f such that f(x_i)=log(x_i) as long as deg(f) is allowed to be arbitrary. If you don't see that you can get a line passing through any two points in the plane (quadratic through any 3 etc), then you missed out on something somewhere.

Of course, less than n and it is impossible (generically), but you did not state that at the start.

You're simply doing some minimization problem in your case, albeit probably a hard one.

Last edited:

- #8

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

But he says he

- #9

- 274

- 0

It's a mess, involves lots of transformations and solving a system of n equations, but I did it. Although my solution is probably not optimal.

Can someone tell me if the rough sketch of it looks ok:

P={polynomials of degree k or less}

T:P->R^N defined by T(p)=(P(x_1),...,p(x_n))

X={T(p): p in P}

X is a k+1 dimensional subspace of R^N, so (T(1),...,T(t^k)) is a basis of X. Use Gram-Schmidt procedures to construct an orthonormal basis and use it to project y=(y_1,..,y_n), and find (b_1,...,b_N)=Y. Solve a1T(1)+...+anT(t^k)=Y and find the coefficients for the polynomial.

Can someone tell me if the rough sketch of it looks ok:

P={polynomials of degree k or less}

T:P->R^N defined by T(p)=(P(x_1),...,p(x_n))

X={T(p): p in P}

X is a k+1 dimensional subspace of R^N, so (T(1),...,T(t^k)) is a basis of X. Use Gram-Schmidt procedures to construct an orthonormal basis and use it to project y=(y_1,..,y_n), and find (b_1,...,b_N)=Y. Solve a1T(1)+...+anT(t^k)=Y and find the coefficients for the polynomial.

Last edited:

Share: