CMPS 251 Homework Assignment 4 Solution, Fall 2015

CMPS 251 Assignment 4‐Solution Problem 1 1) Using bisection method i = 0: a = 0 b = 1    f(a) = 0 – 2e–0 = –2 f(b) = 1 – 2e–1 = 0.26424 c= 0.5 f(c) = 0.5 – 2e–0.5 = –0.71306 i = 1:  a = 0.5 b = 1 c = 0.75 f(c) = 0.75 – 2e–0.75 = –0.19473 i = 2: a = 0.75   b = 1 c = 0.875 f(c) = 0.875 – 2e–0.875 = 0.041276 i = 3 a = 0.75 b = 0.875 c=0.8125 f(c) = 0.8125 – 2e–0.8125 = –0.074995 2) Using Regula Falsi i=0: a=0 b=1 f(a) = 0 – 2e–0 = –2 f(b) = 1 – 2e–1 = 0.26424 c=0.8833 f(c)=0.0565 i=1:a=0 b=0.8833 c=0.8590 f(c)=0.0119 i=2:a=0 b=0.8590 c=0.8539 f(c)=0.00251 i=3:a=0 b=0.8539 c=0.8528 3) Using Secant method x0=0, f(x0)=‐2 x1=1, f(x1)=0.2642 x2=0.8833, f(x2)=0.0564 x3=0.8516, f(x3)=‐1.89 . 10‐3 x4=0.8526127, f(x4)=1.33 . 10‐5 4) Using Newton's method ����� � 1 � 2��� i=1: �� � 1 � �������� ������ � 0.84777 i=2: �� � 0.84777 � �.����������.����� ������.����� � 0.85260 i=3: �� � 0.85260 � �.����������.����� ������.����� � 0.85261 the Matlab code yields r=0.852605502013726. Calculating the relative error, we note that the Newton's method is the fastest followed by the secant method, Regula Falsi and the bisection. Problem 2 Using the Newton's method we have that ������ � �� � ���������� ��������� with �� � ��� ��� � � �� ��  with f and g evaluated at (xn,yn). �� � ��� �� �� ��� , ������ � 1 ���� � ���� � �� ��� ��� �� � ������� � 1 ���� � ���� � �� ��� ��� �� � �� �� � � � � � � ��� � ��� ���� � ���� ��� � ��� ���� � ����� � � � � Replacing in the first equation gives the Newton iterations ����� ����� � ��� ��� � � � � � � ��� � ��� ���� � ���� ��� � ��� ���� � ����� � � � � Thus ���� � �� � ��� � ��� ���� � ���� , ���� � �� � ��� � ��� ���� � ���� Now for the system of equations provided and for the Newton method, we can use the derived Newton iterations with � � �2�� � 3�� � 42, � � 5�� � 3�� � 69 �� � �6��, �� � 6�, �� � 10�, �� � 9�� For 15 iterations, we get the following solution x = 1 y = 1 i = 1 x = 7.6053  y = 0.4386 i = 2 x = 5.0714  y = ‐15.5856 i = 3 x = 5.2462  y = ‐10.4217 i = 4 x = 4.4193  y = ‐6.9736 i = 5 x = 3.7177  y = ‐4.6437 i = 6 x = 3.2126  y = ‐2.9996 i = 7 x = 2.8625  y = ‐1.6460 i = 8 x = 2.5017  y = 0.4757 i = 9 x = 3.3797  y = 8.0452 i =10 x = 3.8073  y = 5.3590 i =11 x = 3.3701  y = 3.6236 i =12 x = 3.1122  y = 2.5926 i =13 x = 3.0173  y = 2.1173 i =14 x = 3.0007  y = 2.0059 i =15 x = 3.0000  y = 2.0000 Now using fixed point iteration x = 1 y = 1 i = 1 x = 2.8231  y = 2.7734 i = 2 x = 3.1925  y = 2.1339 i = 3 x = 3.0304  y = 1.8185 i = 4 x = 2.9610  y = 1.9742 i = 5 x = 2.9943  y = 2.0318 Problem 3 We can use the relations provided in the assignment as follows �� � � � �� ���� � � � ���� � � ���� � ���� � ����� Now using the mean value theorem ����� � ���� � ����� � � �� , �� � � � � ���� � ����� � ������� � ��� ���� � ������� From this relation, if |�����| � 1, the error decreases with each iteration, otherwise it grows. Notice also that if the derivative is positive, the errors will be positive, and hence, the iterative solution will be monotonic. If the derivative is negative, the errors will have a spiraling behavior. Problem 4 Code function f=molermorrison(x,y) f=max([x,y]); a=min([x,y]); for n=1:3 b=(a/f)^2; c=b/(4+b); f=f+2*c*f; a=c*a; end For the second part, you can develop a function as follows function f=molermorrison_norm (x) % x is a vector sum =0; for i=1:length(x) sum=molermorrison(sum,x(i)); end f=sum; Problem 5 function Xs = SteffensenRoot(Fun,Xest,nmax) x(1)=Xest; r_err(1)=0; x(2)=x(1)-(Fun(x(1)))^2/(Fun(x(1)+Fun(x(1)))-Fun(x(1))); r_err(2)=abs((x(2)-x(1))/(x(1))); n=3; while(r_err(n-1)>1e-6 && n< nmax) x(n)=x(n-1)-(Fun(x(n-1)))^2/(Fun(x(n-1)+Fun(x(n-1)))-Fun(x(n-1))); r_err(n)=abs((x(n)-x(n-1))/(x(n-1))); n=n+1; end Xs = x(n-1); fprintf('n x_n f(x_n) Error\n'); fprintf('--------------------------------------------------\n'); for i=2:n-1 fprintf('%2u \t %1.13f \t %e %e\n',i-1,x(i),Fun(x(i)),r_err(i)); end Problem 6 a) �� �� ��� �� �� � � � � . Since α=1 and λ<1, the convergence is linear b) ����.���� �����.��� � � ����.���� ����.���� � 1. Since α=2, the convergence is quadratic c) �������� ���� � � � ���� �� has a limit of 1 as n goes to infinity. It has a sublinear convergence d) ��������� ����� � 10��������� � 10������� has a limit of zero. This has a superlinear convergence. Note that if we try for α>1. 10���������� � 10������������ which has an infinite limit