Ćwiczenie nr 5

Numeryczne rozwiązywanie równań i układów równań nieliniowych

Laboratorium metod numerycznych.

Arkadiusz Milczarek 155725

Mateusz Ziobro 155761

Zadanie 1:

-m-funkcja realizująca metodę bisekcji:
function [x0,x1,n]=bisekcja(F,xa,xb,e)

x0=xa;

x1=xb;

for n=1:25

x=.5*(x0+x1);

a=sign(feval(F,x0)*feval(F,x));

f=feval(F,x);

if a<0

x1=x;

else

x0=x;

end

if f==0

x0=x;

x1=x0;

break

end

warunek=abs(x0-x1);

if warunek<(2*e)

break

end

end

-m-funkcja realizująca metodę siecznych:
function [xo,n]=sieczna(F,x0,x1,e)

x=[1:27];

x=0;

x(1,1)=x0;

x(1,2)=x1;

for n=2:26

x(n+1)=((feval(F,x(n)))*x(n-1)-(feval(F,x(n-1)))*x(n))/((feval(F,x(n)))-(feval(F,x(n-1))));

warunek=abs(x(n)-x(n-1));

if warunek<e

break

end

end

xo=x;

-m-funkcja realizująca metodę Newtona:
function [xo,n]=newton(F,Fd,x0,e)

x=[1:26];

x=0;

x(1,1)=x0;

for n=2:26

x(n)=x(n-1)-(feval(F,x(n-1))/feval(Fd,x(n-1)));

warunek=abs(x(n)-x(n-1));

if warunek<e

break

end

end

xo=x;

funkcja: f(x)=atan(4x)-πx; x'=0,25
metoda Newtona: x₀=0,3, przyjmuję ε=1e-16
uzyskane przybliżenia:

n	x	|x-x'|	f(x)	f'(x)
0	0.300000000000000	0.050000000000000	-0.066419745478745	-1.502248391294711
1	0.255786442599216	0.005786442599216	-0.006738658879160	-1.187348607914774
2	0.250111058946732	0.000111058946732	-0.000126833406758	-1.142480927818234
3	0.250000043170740	0.000000043170740	-0.000000049283407	-1.141592998955683
4	0.250000000000007	0.000000000000007	-0.000000000000008	-1.141592653589849
5	0.250000000000000	0	0	-1.141592653589793
6	0.250000000000000	0	0	-1.141592653589793

Metoda siecznych: x₀=0,3,x₁=0,29 ; przyjmuję ε=1e-16
uzyskane przybliżenia:

n	x	|x-x'|	f(x)	f'(x)
0	0.300000000000000	0.050000000000000	-0.066419745478745	-1.502248391294711
1	0.290000000000000	0.040000000000000	-0.051724668485651	-1.436272053316942
2	0.254801362721704	0.004801362721704	-0.005572822484048	-1.179634772750672
3	0.250551137124541	0.000551137124541	-0.000630388208170	-1.145996890563825
4	0.250009037432576	0.000009037432576	-0.000010317393333	-1.141664951743598
5	0.250000017405163	0.000000017405163	-0.000000019869607	-1.141592792831092
6	0.250000000000551	0.000000000000551	-0.000000000000629	-1.141592653594201
7	0.250000000000000	0	0	-1.141592653589793
8	0.250000000000000	0	0	-1.141592653589793
9	0.250000000000000	0	0	-1.141592653589793

Metoda bisekcji: x_a=0,225,x_b=0,3 ; przyjmuję ε=1e-16
uzyskany przedział zawierający poszukiwany pierwiastek:

n	xa	xb	~x	|~x-x'|	f(x)	f'(x)
0	0.225000000000000	0.300000000000000	0.262500000000000	0.012500000000000	-0.014884498997154	-1.239095626241398
1	0.225000000000000	0.262500000000000	0.243750000000000	0.006250000000000	0.006977402250884	-1.090967853846121
2	0.243750000000000	0.262500000000000	0.253125000000000	0.003125000000000	-0.003606376789602	-1.166436415645190
3	0.243750000000000	0.253125000000000	0.248437500000000	0.001562500000000	0.001773952551422	-1.129053591857516
4	0.248437500000000	0.253125000000000	0.250781250000000	0.000781250000000	-0.000894308123743	-1.147832888012328
5	0.248437500000000	0.250781250000000	0.249609375000000	0.000390625000000	0.000445323960855	-1.138465212186528
6	0.249609375000000	0.250781250000000	0.250195312500000	0.000195312500000	-0.000223119863308	-1.143154543238417
7	0.249609375000000	0.250195312500000	0.249902343750000	0.000097656250000	0.000111445505637	-1.140811251001914
8	0.249902343750000	0.250195312500000	0.250048828125000	0.000048828125000	-0.000055751364911	-1.141983240442821
9	0.249902343750000	0.250048828125000	0.249975585937500	0.000024414062500	0.000027868530131	-1.141397331553050
10	0.249975585937500	0.250048828125000	0.250012207031250	0.000012207031250	-0.000013936053234	-1.141690307455607
11	0.249975585937500	0.250012207031250	0.249993896484375	0.000006103515625	0.000006967579586	-1.141543824868747
12	0.249993896484375	0.250012207031250	0.250003051757813	0.000003051757813	-0.000003483901553	-1.141617067503286
13	0.249993896484375	0.250003051757813	0.249998474121094	0.000001525878906	0.000001741922836	-1.141580446521292
14	0.249998474121094	0.250003051757813	0.250000762939454	0.000000762939454	-0.000000870968404	-1.141598757096112
15	0.249998474121094	0.250000762939453	0.249999618530274	0.000000381469726	0.000000435482455	-1.141589601829657
16	0.249999618530273	0.250000762939453	0.250000190734863	0.000000190734863	-0.000000217741664	-1.141594179468115
17	0.249999618530273	0.250000190734863	0.249999904632568	0.000000095367432	0.000000108870723	-1.141591890650192
18	0.249999904632568	0.250000190734863	0.250000047683716	0.000000047683716	-0.000000054435389	-1.141593035059485
19	0.249999904632568	0.250000047683716	0.249999976158142	0.000000023841858	0.000000027217688	-1.141592462854920
20	0.249999976158142	0.250000047683716	0.250000011920929	0.000000011920929	-0.000000013608845	-1.141592748957223
21	0.249999976158142	0.250000011920929	0.249999994039536	0.000000005960464	0.000000006804422	-1.141592605906080
22	0.249999994039536	0.250000011920929	0.250000002980233	0.000000002980233	-0.000000003402212	-1.141592677431657
23	0.249999994039536	0.250000002980232	0.249999998509884	0.000000001490116	0.000000001701106	-1.141592641668865
24	0.249999998509884	0.250000002980232	0.250000000745058	0.000000000745058	-0.000000000850553	-1.141592659550257
25	0.249999998509884	0.250000000745058	0.249999999627471	0.000000000372529	0.000000000425276	-1.141592650609561

funkcja: f(x)=2(cos(πx)+πx)-π; x'=0,5

metoda Newtona: x₀=0,45, przyjmuję ε=1e-16
uzyskane przybliżenia:

n	x	|x-x'|	f(x)	f'(x)
0	0.450000000000000	0.050000000000000	-0.001290335278517	0.077356437479629
1	0.466680386539998	0.033319613460002	-0.000382111660873	0.034391643997409
2	0.477790982500501	0.022209017499499	-0.000113190686121	0.015287346930514
3	0.485195189825382	0.014804810174618	-0.000033534352015	0.006794805237289
4	0.490130482426739	0.009869517573261	-0.000009935626597	0.003019998129124
5	0.493420427046784	0.006579572953216	-0.000002943826466	0.001342238118304
6	0.495613649267198	0.004386350732802	-0.000000872236597	0.000596553578924
7	0.497075775432463	0.002924224567537	-0.000000258439383	0.000265135576713
8	0.498050519697216	0.001949480302784	-0.000000076574488	0.000117838163002
9	0.498700347275429	0.001299652724571	-0.000000022688718	0.000052372542505
10	0.499133565090996	0.000866434909004	-0.000000006722581	0.000023276690589
11	0.499422376796791	0.000577623203209	-0.000000001991876	0.000010345196878
12	0.499614917893583	0.000385082106417	-0.000000000590185	0.000004597865287
13	0.499743278599523	0.000256721400477	-0.000000000174869	0.000002043495761
14	0.499828852279481	0.000171147720519	-0.000000000051813	0.000000908221641
15	0.499885901371951	0.000114098628049	-0.000000000015352	0.000000403655113
16	0.499923934245793	0.000076065754207	-0.000000000004549	0.000000179402284
17	0.499949289585043	0.000050710414957	-0.000000000001348	0.000000079734073
18	0.499966193409300	0.000033806590700	-0.000000000000399	0.000000035436626
19	0.499977459611641	0.000022540388359	-0.000000000000118	0.000000015753331
20	0.499984958199031	0.000015041800969	-0.000000000000035	0.000000007015349
21	0.499989959097294	0.000010040902706	-0.000000000000010	0.000000003126044
22	0.499993226501977	0.000006773498023	-0.000000000000003	0.000000001422577
23	0.499995411708876	0.000004588291124	-0.000000000000001	0.000000000652757
24	0.499996772366019	0.000003227633981	-0.000000000000000	0.000000000323012
25	0.499998147204819	0.000001852795181	0	0.000000000106440

Metoda siecznych: x₀=45,x₁=0,46; przyjmuję ε=1e-16
uzyskane przybliżenia:

n	x	|x-x'|	f(x)	f'(x)
0	0.450000000000000	0.050000000000000	-0.001290335278517	0.077356437479629
1	0.460000000000000	0.040000000000000	-0.000660945158575	0.049544792843595
2	0.470501358976451	0.029498641023549	-0.000265184354049	0.026961422066286
3	0.477537922640549	0.022462077359451	-0.000117103529977	0.015637568603226
4	0.483102494887798	0.016897505112202	-0.000049858008814	0.008851009379184
5	0.487228249099303	0.012771750900697	-0.000021530034370	0.005056991595440
6	0.490363934997220	0.009636065002780	-0.000009247144119	0.002878829160364
7	0.492724628516264	0.007275371483736	-0.000003979995123	0.001641122721624
8	0.494508430094395	0.005491569905605	-0.000001711636146	0.000935043636232
9	0.495854433654728	0.004145566345272	-0.000000736336434	0.000532857667445
10	0.496870645850358	0.003129354149642	-0.000000316730882	0.000303637600244
11	0.497637713356012	0.002362286643988	-0.000000136246373	0.000173026576073
12	0.498216766742610	0.001783233257390	-0.000000058607359	0.000098597247835
13	0.498653876738543	0.001346123261457	-0.000000025210558	0.000056184772796
14	0.498983842088467	0.001016157911533	-0.000000010844555	0.000032016337901
15	0.499232925106367	0.000767074893633	-0.000000004664891	0.000018244205060
16	0.499420952349224	0.000579047650776	-0.000000002006648	0.000010396283318
17	0.499562889856111	0.000437110143889	-0.000000000863179	0.000005924221939
18	0.499670035375249	0.000329964624751	-0.000000000371305	0.000003375859343
19	0.499750917060414	0.000249082939586	-0.000000000159720	0.000001923700957
20	0.499811972762683	0.000188027237317	-0.000000000068705	0.000001096203377
21	0.499858062149737	0.000141937850263	-0.000000000029554	0.000000624663396
22	0.499892853990803	0.000107146009197	-0.000000000012713	0.000000355960340
23	0.499919117367494	0.000080882632506	-0.000000000005469	0.000000202843069
24	0.499938942489823	0.000061057510177	-0.000000000002352	0.000000115592005
25	0.499953908098057	0.000046091901943	-0.000000000001012	0.000000065871700
26	0.499965209165375	0.000034790834625	-0.000000000000435	0.000000037530065

Metoda bisekcji: x_a=0,45,x_b=0,6 ; przyjmuję ε=1e-16
uzyskany przedział zawierający poszukiwany pierwiastek:

n	xa	xb	x	|x-x'|	f(x)	f'(x)
0	0.450000000000000	0.600000000000000	0.525000000000000	0.025000000000000	0.161441223800018e-3	0.019368963394949
1	0.450000000000000	0.525000000000000	0.487500000000000	0.012500000000000	-0.020184821607483e-3	0.004844108164658
2	0.487500000000000	0.525000000000000	0.506250000000000	0.006250000000000	0.002523248615827e-3	0.001211143770909
3	0.487500000000000	0.506250000000000	0.496875000000000	0.003125000000000	-0.000315410636720e-3	0.000302793238688
4	0.496875000000000	0.506250000000000	0.501562500000000	0.001562500000000	0.000039426472309e-3	0.000075698765674
5	0.496875000000000	0.501562500000000	0.499218750000000	0.000781250000000	-0.000004928313313e-3	0.000018924719919
6	0.499218750000000	0.501562500000000	0.500390625000000	0.000390625000000	0.000000616039664e-3	0.000004731181761
7	0.499218750000000	0.500390625000000	0.499804687500000	0.000195312500000	-0.000000077004625e-3	0.000001182795551
8	0.499804687500000	0.500390625000000	0.500097656250000	0.000097656250000	0.000000009625634e-3	0.000000295698895
9	0.499804687500000	0.500097656250000	0.499951171875000	0.000048828125000	-0.000000001203038e-3	0.000000073924724
10	0.499951171875000	0.500097656250000	0.500024414062500	0.000024414062500	0.000000000150546e-3	0.000000018481181
11	0.499951171875000	0.500024414062500	0.499987792968750	0.000012207031250	-0.000000000018652e-3	0.000000004620295
12	0.499987792968750	0.500024414062500	0.500006103515625	0.000006103515625	0.000000000002665e-3	0.000000001155074
13	0.499987792968750	0.500006103515625	0.499996948242188	0.000003051757812	0	0.000000000288768
14	0.499996948242188	0.500006103515625	0.500001525878907	0.000001525878907	0	0.000000000072192
15	0.499996948242188	0.499996948242188	0.499996948242188	0.000003051757812	0	0.000000000288768

Zadanie 2:

zastępuję funkcje f(x) wyrażeniem g(x)=f(x)/f'(x)
g(x) =(2*(cos(pi*x)+pi*x)-pi)/(2*(pi-pi*sin(pi*x)))

g'(x)=pi^2*cos(pi*x)*(2*(cos(pi*x)+pi*x)-pi)/(2*(pi-pi*sin(pi*x))^2)+1

metoda Newtona: x₀=0,45, przyjmuję ε=1e-4
uzyskane przybliżenia:

n	x	|x-x'|	g(x)	g'(x)
0	0.450000000000000	0.050000000000000	-0.016680386539998	0.334157009709169
1	0.499917811254403	-8.218874559701161e-005	-2.739630712961191e-005	0.333331913401343
2	0.500000000525901	0.000000000525901	-	-

Metoda siecznych: x₀=45,x₁=0,46; przyjmuję ε=1e-4
uzyskane przybliżenia:

n	x	|x-x'|	g(x)	g'(x)
0	0.450000000000000	0.050000000000000	-0.016680386539998	0.334157009709169
1	0.460000000000000	0.040000000000000	-0.013340355678978	0.333860207376031
2	0.499940815621398	0.000059184378602	-1.972893933885572e-005	0.333305857416946
3	0.499999971241020	0.000000028758980	0	1
4	0.499999971241020	0.000000028758980	0	1

n	xa	xb	x	|x-x'|	f(x)	f'(x)
0	0.450000000000000	0.600000000000000	0.525000000000000	0.025000000000000	0.008335047183894	0.333539025609309
1	0.450000000000000	0.525000000000000	0.487500000000000	0.012500000000000	-0.004166880862560	0.333384742246212
2	0.487500000000000	0.525000000000000	0.506250000000000	0.006250000000000	0.002083360106729	0.333346184671995
3	0.487500000000000	0.506250000000000	0.496875000000000	0.003125000000000	-0.001041670012471	0.333336546647037
4	0.496875000000000	0.506250000000000	0.501562500000000	0.001562500000000	0.000520833754129	0.333334133363029
5	0.496875000000000	0.501562500000000	0.499218750000000	0.000781250000000	-0.000260416710739	0.333333555175561
6	0.499218750000000	0.501562500000000	0.500390625000000	0.000390625000000	0.000130208411945	0.333333014509564
7	0.499218750000000	0.500390625000000	0.499804687500000	0.000195312500000	-0.000065103918268	0.333335897675264
8	0.499804687500000	0.500390625000000	0.500097656250000	0.000097656250000	0.000032552146105	0.333332052656128
9	0.499804687500000	0.500097656250000	0.499951171875000	0.000048828125000	-0.000016273820211	0.333424325201577
10	0.499951171875000	0.500097656250000	0.500024414062500	0.000024414062500	0.000008145921080	0.332686144199632

Metoda bisekcji: x_a=0,45,x_b=0,6 ; przyjmuję ε=1e-4
uzyskany przedział zawierający poszukiwany pierwiastek:

Zadanie 3:

funkcja			Punkt przybliżony		pierwiastek
atan(4x)-πx			0,3		1/4
2(cos(πx)+πx)-π;			0,45		1/2
g(x)			0,0 0,3 1,0 2,0		0,499999970638815 0,500000031610662 0.499999928018106 0.499999960856419
-	roots		Bairstow					Laguerre
-	-		e=1e-7		e=1e-5	e=1e-9		e=1e-3	e=1e-5	e=1e-9
-	Wynik		wynik		wynik	wynik		wynik	wynik	wynik
1	5.0000		5.0000		5.0001	5.0000		5.0000-0.0000i	-3.0000-0.0000i	5.0000
2	-3.0000		-3.0000		-3.0000	-3.0000		-3.0000-0.0000i	5.0000+0.0000i	-3.0000
3	-2.0000+1.0000i		-2.0000+1.0000i		-2.0000+1.0000i	-2.0000+1.0000i		-2.0000+1.0000i	-2.0000+1.0000i	-2.0000+1.0000i
4	-2.0000-1.0000i		-2.0000-1.0000i		-2.0000-1.0000i	-2.0000-1.0000i		-2.0000-1.0000i	-2.0000-1.0000i	-2.0000-1.0000i
5	1.0000+2.0000i		1.0007+2.0016i		1.0059+2.0006i	1.0004+1.9997i		1.0003+2.0007i	1.0000+2.0000i	1.0004+1.9997i
6	1.0000-2.0000i		1.0007-2.0016i		0.9941-1.9994i	0.9996-2.0003i		1.0001-1.9991i	1.0000-2.0000i	1.0004-1.9997i
7	1.0000+2.0000i		0.9993+1.9984i		0.9941+1.9994i	0.9996+2.0003i		0.9997+1.9993i	1.0000+2.0000i	0.9996+2.0003i
8	1.0000-2.0000i		0.9993-1.9984i		1.0059-2.0006i	1.0004-1.9997i		0.9999-2.0009i	1.0000-2.0000i	0.9996-2.0003i
9	2.0000		2.0000		2.0000	2.0000		1.9995	2.0000	2.0000
10	2.0000+0.0000i		2.0000		2.0000	2.0000		1.9995	2.0000	2.0000
11	2.0000-0.0000i		2.0000		2.0000	2.0000		2.0010	2.0000	2.0000

Zadanie 4:

x¹¹-8x¹⁰+12x⁹+50x⁸-250x⁷+318x⁶+696x⁵-2396x⁴+585x³+9050x²-20500x+15000

Obliczenie pojedynczych pierwiastków rzeczywistych metodami Newtona oraz siecznych:

pierwiastek	Newton
-	=1e-3	=1e-5	=1e-9
-3	-2.999797578075429	-2.999797451117349	-2.999797451117308
błąd	0.202421924571095*1e-3	0.202548882651143*1e-3	0.202548882692000*1e-3
5	5.000289239960210	5.000289234294820	5.000289234294821
błąd	0.289239960210352*1e-3	0.289234294820417*1e-3	0.289234294821306*1e-3
siecznych
-	=1e-3	=1e-5	=1e-9
-3	-2.999797451214289	-2.999797451117309	-2.999797451117308
błąd	0.202548785710910*1e-3	0.202548882691111*1e-3	0.202548882692000*1e-3
5	5.000289234363209	5.000289234294821	5.000289234294819
błąd	0.289234363209268*1e-3	0.289234294821306*1e-3	0.289234294818641*1e-3

Zadanie 5
Pierwiastki wielomianu obliczone za pomocą metody Lehmera-Schura. (ε=1e-12):
1.999998089122121 - 0.000012725903321i

2.000011976354295 + 0.000004707977694i

1.999989934523591 + 0.000008017925382i

1.000000291634885 + 1.999999715427233i

0.999999708364844 + 2.000000284572781i

-2.000000000001699 + 0.999999999999590i

-3.000000000000238 - 0.000000000001662i

-1.999999999997121 - 0.999999999999669i

1.000000572678304 - 2.000001846123856i

0.999999427320878 - 1.999998153873953i

5.000000000000139 - 0.000000000000218i

Wnioski:

Celem zadania pierwszego było napisanie m-funkcji realizujących metody bisekcji, Newtona oraz siecznych, a następnie przetestowanie ich na podanych zadaniach. W celu analizy szybkość metody dla każdej z metod przyjąłem stalą wartość ε=1e-16. Z analizy przeprowadzonych pomiarów wynika, że najszybsza jest metoda Newtona, metoda siecznych jest nieco wolniejsza, natomiast metoda bisekcji jest najwolniejsza. Metoda bisekcji zwraca najmniejszy przedział w którym znajduje się poszukiwany pierwiastek. W przypadku gdy granice przedziału są sobie równe oznacza to że jest to dokładny pierwiastek. Taki przypadek możemy dostrzec w obliczeniach pierwiastka drugiej funkcji. Obliczony pierwiastek jest obarczony błędem spowodowanym błędami zaokrągleń, oraz nakładaniem się na siebie błędów w wyniku wielokrotnych operacji arytmetycznych.
Do zadania 2 przyjąłem ε=1e-4 spowodowane było to tym, że dla większej liczby iteracji pojawiało się działanie zabronione: 0/0 (bardzo małe liczby bliskie 0). Zastosowanie podstawienia znacznie przyspieszyło obliczenie poszukiwanego pierwiastka, zadowalający wynik uzyskujemy już po kilku iteracjach (2-3).W tym przypadku metoda Newtona także była najszybsza.
Funkcja fzero pozwala na znalezienie dokładnej wartość pierwiastka w okolicy określonego punktu. Na przykładzie obliczenia pierwiastka funkcji g(x) widać, że pomimo wzięcia do obliczeni różnych punktów wyniki różnią się nieznacznie są stosunkowo dokładne.
Funkcja roots zwraca pierwiastki wielomianu. Uzyskane wyniki posiadają dużą dokładność. Podany wielomian posiada 5 pierwiastków rzeczywistych. Funkcje Laguerre'a i Bairstow'a także pozwalają na obliczenie pierwiastków wielomiany w zadaną dokładnością. Metody te dokładnie obliczają pierwiastki rzeczywiste, natomiast pierwiastki zespolone obarczone są większym błędem.
Do poszukiwania pierwiastków rzeczywistych wielomianu można zastosować metodę Newtona, oraz siecznych. Warunkiem jest aby znacz otoczenie w jaki się znajdują poszukiwane pierwiastki. Jednak pierwiastki te są obarczone większym błędem niż w przypadku zastosowania innych metod.
W przypadku zastosowania metody Lehmera-Schura pierwiastki są stosunkowo dokładnie obliczone. Z tą różnicą że każdy z nich jest traktowany jako pierwiastek zespolony, z racji tego że pierwiastki są poszukiwane na płaszczyźnie zespolonej. Pomimo tego ze podany wielomian posiada 5 pierwiastków rzeczywistych z metody tej wynika ze wszystkie pierwiastki są pierwiastkami zespolonymi.

---