User:SigmaJargon/Math5610Assignment4

1.) Spline vs. Cubic Hermite

a.) Data:

$s(0)=1$

$s'(0)=1$

$s(1)=2$

$s'(1)=y$

$s(2)=2$

$s'(2)=0$

The coefficients of the piecewise cubic function on the first interval (0-1) are found by solving:

${\begin{bmatrix}0&0&0&1\\0&0&1&0\\1&1&1&1\\3&2&1&0\\\end{bmatrix}}{\begin{bmatrix}a\\b\\c\\d\\\end{bmatrix}}={\begin{bmatrix}1\\1\\2\\y\\\end{bmatrix}}$

And on the second interval (1-2):

${\begin{bmatrix}1&1&1&1\\3&2&1&0\\8&4&2&1\\12&4&1&0\\\end{bmatrix}}{\begin{bmatrix}a\\b\\c\\d\\\end{bmatrix}}={\begin{bmatrix}2\\y\\2\\0\\\end{bmatrix}}$

b.) This becomes a cubic spline if the second derivative is continuous. Since we only have two intervals, this will hold if the second derivative for both equations is equal at 1. That is, if:

$6(y-1)-2(y-1)=6y-10y$

$4y-4=-4y$

$8y=4$

$y=1/2$

2.) More on Cubic Splines

Data:

$(x_{1},y_{1})=(1,1)$

$(x_{2},y_{2})=(2,8)$

$(x_{3},y_{3})=(3,27)$

$(x_{4},y_{4})=(4,64)$

a.) I'm not sure I should even bother solving the system of equations to find the coefficients - it's pretty obvious that $x^{3}$ is what we're looking for.

b.)

${\begin{bmatrix}1&1&1&1&0&0&0&0&0&0\ \ 0\ \ 0\\8&4&2&1&0&0&0&0&0&0\ \ 0\ 0\\0&0&0&0&8&4&2&1&0&0\ \ 0\ \ 0\\0&0&0&0&27&9&3&1&0&0\ \ 0\ \ 0\\0&0&0&0&0&0&0&0&27&9\ \ 3\ \ 1\\0&0&0&0&0&0&0&0&64&16\ \ 4\ \ 1\\12&4&1&0&-12&-4&-1&0&0&0\ \ 0\ \ 0\\0&0&0&0&27&6&1&0&-27&-6\ \ -1\ \ 0\\12&2&0&0&-12&-2&0&0&0&0\ \ 0\ \ 0\\0&0&0&0&18&2&0&0&-18&-2\ \ 0\ \ 0\\6&2&0&0&0&0&0&0&0&0\ \ 0\ \ 0\\0&0&0&0&0&0&0&0&24&2\ \ 0\ \ 0\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\b_{1}\\c_{1}\\d_{1}\\a_{2}\\b_{2}\\c_{2}\\d_{2}\\a_{3}\\b_{3}\\c_{3}\\d_{3}\\\end{bmatrix}}={\begin{bmatrix}1\\8\\8\\27\\27\\64\\0\\0\\0\\0\\0\\0\\\end{bmatrix}}$

which yields the polynomial:

$P(x)={\begin{cases}2x^{3}-6x^{2}+11x-6,&if\ x\leq 2\\2x^{3}-6x^{2}+11x-6,&if\ 2<x\leq 3\\-4x^{3}+48x^{2}-151x+156,&if\ 3<x\end{cases}}$

c.)

3.) Linear Programming

At first glance, I'd've said no. First of all, Meg has less than a shining record in terms of trying to squeeze money out of me for bogus solutions, and second, the claim that the speed is independent of the size of the problem is indeed stunning.

However, it never hurts to give her the benefit of the doubt. Let's work through it a bit and see how we feel after some analysis.

First off, on the transformation of an inequality constraint to an equality constraint: if we require that $Ax\leq b$, then it follows that $Ax+y=b$ for some "slack" vector $y>0$. A sign constraint is really just an inequality constraint, and can be treated in a similar way.

${\displaystyle }$

5.) Runge Interpolation and 6.) Judicious Interpolation

Uploading the 40 images for these two questions would be a headache and a chore. Therefore I provide 4 images - the interpolations at n=10 and n=20. If you'd like to generate more, then you can use these Maple worksheets I created:

Runge Interpolation

Judicious Interpolation

10th degree Runge

File:Runge10.jpg

20th degree Runge

File:Runge20.jpg

10th degree Judicious

File:Judicious10.jpg

20th degree Judicious

File:Judicious20.jpg

7.) Interpolation of Symmetric Data is Symmetric

We're interpolating over 2n+1 points, so we'll need a polynomial of degree 2n+1. Since n is a natural number, we then have that the interpolating polynomial is of odd degree.

For the sake of contradiction, let's say that the interpolate isn't odd. Then there is some point $x_{s}$ along the curve so that $P(x_{s})\neq -p(-x_{s})$. $x_{s}$ cannot be any of the interpolating points, since $P(x_{i})=y_{i}=-y_{-i}=-P(-x_{-i})$. We can define $P'(x)$ by rotating $P(x)$ 180 degrees - that is, $P'(x)=-P(-x)$. All of the interpolating points lie along this polynomial, since $P'(x_{i})=-P(-x_{i})=P(x_{-i})$ for all i. However, since $P(x_{s})\neq -P(-x_{s})$, the point $P'(x_{s})=-P(-x_{s})\neq P(x_{s})$, so $P(x)$ and $P'(x)$ are different polynomials. However, the interpolating polynomial is unique! Thus we have a contradiction, and it is proved that $P(x)$ is odd.

8.) Linear Independence of Bernstein-Bezier Basis Functions

The first and most important thing to note is that for Bersteing-Bezier basis functions is that if you expand the $(1-x)^{n-i}$, you always end up with a 1, plus a bunch of higher order terms. If you then multiply with $x^{i},thelowestorderterminthatbasisfunctionisorderi.Furthermore,itisthelastbasisfunctiontocontainatermoforderi,becausewenotethatthei+1thbasisfunction'slowesttermis<math>x^{i+1}$, and so on.

Then consider $c_{0}$. The 0th basis function contains a non-zero term of order 0 (that is, constant). However, it is the last and thus the only basis function to contain such a term, and so since the sum of all basis functions is zero we conclude $c_{0}=0$.

We then assume the $c_{0}=0,...,c_{k-2}=0,\ c_{k-1}=0$, and then seek a proof that $c_{k}=0$. Consider the kth basis function. It is the last basis function to contain a term of order k. In the sum of basis functions, all basis functions less than the kth are 0, since $c_{0}=0,...,c_{k-2}=0,\ c_{k-1}=0$. So the kth basis function is the only non-zero function contributing a term of order k to the sum. However, since the sum equals 0, we conclude that $c_{k}=0$.

Thus, by induction, $c_{i}=0$ for all i.

9.) Uniqueness of Interpolating Polynomial

a.) Power Form

${\begin{bmatrix}1&1&1&1\\8&4&2&1\\64&16&4&1\\512&64&8&1\\\end{bmatrix}}{\begin{bmatrix}a\\b\\c\\d\\\end{bmatrix}}={\begin{bmatrix}1\\2\\3\\4\\\end{bmatrix}}$

This yield $a=1/56$, $b=-7/24$, $c=7/4$, and $d=-10/21$. So $P(x)=x^{3}/56-7x^{2}/24+7x/4-10/21$.

b.) Lagrange Form

$L_{1}={\frac {(x-2)(x-4)(x-8)}{(1-2)(1-4)(1-8)}}$

$L_{2}={\frac {(x-1)(x-4)(x-8)}{(2-1)(2-4)(2-8)}}$

$L_{3}={\frac {(x-1)(x-2)(x-8)}{(4-1)(4-2)(4-8)}}$

$L_{4}={\frac {(x-1)(x-2)(x-4)}{(8-1)(8-2)(8-4)}}$

So $P(x)=1*L_{1}+2*L_{2}+3*L_{3}+4*L_{4}\,\!$. Substituting and simplifying everything down leaves us with: $P(x)=7/4*x-7/24*x^{2}-10/21+1/56*x^{3}$

c.) Newton Form

$P(x)=b_{0}+b_{1}(x-x_{0})+b_{2}(x-x_{0})(x-x_{1})+b_{3}(x-x_{0})(x-x_{1})(x-x_{2})$

$P(x_{0})=b_{0}$

$P(x_{1})=b_{0}+b_{1}(x_{1}-x_{0})$

$P(x_{2})=b_{0}+b_{1}(x_{2}-x_{0})+b_{2}(x_{2}-x_{0})(x_{2}-x_{1})$

$P(x_{3})=b_{0}+b_{1}(x_{3}-x_{0})+b_{2}(x_{3}-x_{0})(x_{3}-x_{1})+b_{3}(x_{3}-x_{0})(x_{3}-x_{1})(x_{3}-x_{2})$

$1=b_{0}$

$2=b_{0}+b_{1}(2-1)=1+b_{1}$

$1=b_{1}$

$3=b_{0}+b_{1}(4-1)+b_{2}(4-1)(4-2)=1+1(4-1)+b_{2}(4-1)(4-2)=4+6b_{2}$

$-1/6=b_{2}$

$4=b_{0}+b_{1}(8-1)+b_{2}(8-1)(8-2)+b_{3}(8-1)(8-2)(8-4)=1+7-1+168b_{3}$

$1/56=b_{3}$

So, $P(x)=1+(x-1)-(x-1)(x-2)/6+(x-1)(x-2)(x-4)/56$. If we expand all the terms and then simplify, we arrive at: $P(x)=7/4*x-7/24*x^{2}-10/21+1/56*x^{3}$

10.) The Method of Undetermined Coefficients

We expect that since we have four points, we'll at least have accuracy up to cubic functions. We then want to check if we can find values for $a_{0},\ a_{1},\ a_{2},\ a_{3}$ such that the we have exactness for quartic polynomials.

I claim that there are no $a_{0},\ a_{1},\ a_{2},\ a_{3}$ that fulfill the conditions. To show this, consider this counter-example:

Let $a=0,\ h=1$. In order to find $a_{0},\ a_{1},\ a_{2},\ a_{3}$, let's throw four specific functions at the equality, and see what $a_{0},\ a_{1},\ a_{2},\ a_{3}$ turn up.

$f_{0}(x)=x^{4}\,\!$

$f_{0}(x)=x^{4}+1\,\!$

$f_{0}(x)=x^{4}+2\,\!$

$f_{0}(x)=x^{4}+3\,\!$

$\int _{0}^{1}f(x)\,dy=a_{0}f(0)+a_{1}f(1/3)+a_{2}f(1/2)+a_{3}f(1)$. Plugging in the four functions above yields:

$1/5=0a_{0}+a_{1}/81+a_{2}/16+1a_{3}\,\!$

$6/5=1a_{0}+82a_{1}/81+17a_{2}/16+2a_{3}\,\!$

$11/5=2a_{0}+163a_{1}/81+33a_{2}/16+3a_{3}\,\!$

$16/5=3a_{0}+244a_{1}/81+49a_{2}/16+4a_{3}\,\!$

Or, in matrix form:

${\begin{bmatrix}0&1/81&1/16&1\\1&82/81&17/16&2\\2&163/81&33/16&3\\3&244/81&49/16&4\\\end{bmatrix}}{\begin{bmatrix}a\\b\\c\\d\\\end{bmatrix}}={\begin{bmatrix}1/5\\6/5\\11/5\\16/5\\\end{bmatrix}}$

${\begin{bmatrix}a\\b\\c\\d\\\end{bmatrix}}={\begin{bmatrix}0.0750651\\-0.5958984\\1.4010417\\0.1197917\\\end{bmatrix}}$

However, if we consider a slightly different set of functions

$f_{0}(x)=x^{4}+1\,\!$

$f_{0}(x)=x^{4}+2\,\!$

$f_{0}(x)=x^{4}+3\,\!$

$f_{0}(x)=x^{4}+5\,\!$

And try to find $a_{0},\ a_{1},\ a_{2},\ a_{3}$, we get:

${\begin{bmatrix}a\\b\\c\\d\\\end{bmatrix}}={\begin{bmatrix}0.7980469\\1.1707031\\-1.2312500\\0.2625000\\\end{bmatrix}}$

Which is different! So we can't find a solution for $a_{0},\ a_{1},\ a_{2},\ a_{3}$ that works for all quartic functions. And if we can't find working weights for quartic function we aren't going to find them for higher order polynomials.

So! We now want to find the $a_{0},\ a_{1},\ a_{2},\ a_{3}$ for cubic functions!

To do so, we use the procedure described in the 10/25 lecture.

$L_{0}={\frac {(x-(t+h/3))(x-(t+h/2))(x-(t+h))}{(t-(t+h/3))(t-(t+h/2))(t-(t+h))}}$

$L_{1}={\frac {(x-t)(x-(t+h/2))(x-(t+h))}{((t+h/3)-t)((t+h/3)-(t+h/2))((t+h/3)-(t+h))}}$

$L_{2}={\frac {(x-t)(x-(t+h/3))(x-(t+h))}{((t+h/2)-t)((t+h/2)-(t+h/3))((t+h/2)-(t+h))}}$

$L_{3}={\frac {(x-t)(x-(t+h/2))(x-(t+h/3))}{((t+h)-t)((t+h)-(t+h/2))((t+h)-(t+h/3))}}$

$\int _{t}^{t+h}f(x)\,dx\approx \int _{t}^{t+h}L_{0}f(t)+L_{1}f(t+h/3)+L_{2}f(t+h/2)+L_{3}f(t+h)\,dx$

$=f(t)\int _{t}^{t+h}L_{0}\,dx+f(t+h/3)\int _{t}^{t+h}L_{1}\,dx+f(t+h/2)\int _{t}^{t+h}L_{2}\,dx+f(t+h)\int _{t}^{t+h}L_{3}\,dx$

${\displaystyle }$

12.) The Method of Undetermined Coefficients, Continued

Wait wait wait. h has no relation to the point we're considering. So it is arbitrary, another number we can also pick so as to maximize our polynomial degree. Since this is so, it quickly falls out that this formula is accurate for polynomials of degree as high as we wish: simply set $a_{0}=1,\ a_{1}=a_{2}=0,\ a_{3}=-1$. Then we have $f'(a)={\frac {f(a)-f(a+h)}{h}}$. Of course, you should see where this is going - simply take a small h, or in general the limit as h goes to 0, and we have that $f'(a)=\lim _{h\to 0}{\frac {f(a)-f(a+h)}{h}}$. This we know to be true, as it is the definition of the derivative.