Þ±cell_dependenciesÞEÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2„´precedence_heuristic §cell_idÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2„´precedence_heuristic §cell_idÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3„´precedence_heuristic §cell_idÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$990863df-8549-434a-acb0-22207a4df287„´precedence_heuristic§cell_idÙ$990863df-8549-434a-acb0-22207a4df287´downstream_cells_map«Polynomials‘Ù$990863df-8549-434a-acb0-22207a4df287²upstream_cells_map‹¸LaTeXStrings.latexstring¤rate‘Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458«temperature‘Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458¡N‘Ù$f01345c5-3b96-40f1-8ed3-0fbe85f908d9¯Polynomials.fit¬LaTeXStrings‘Ù$c9aac823-6556-4a98-92e4-7e8631e7b71e¨scatter!¦vline!¦@L_str«Polynomials‘Ù$990863df-8549-434a-acb0-22207a4df287¤plotÙ$ed573aed-09e2-47ff-8b91-fdd14f3bee0f„´precedence_heuristic §cell_idÙ$ed573aed-09e2-47ff-8b91-fdd14f3bee0f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$86590ede-19cd-4610-baa4-eb3f1286bd67„´precedence_heuristic §cell_idÙ$86590ede-19cd-4610-baa4-eb3f1286bd67´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542b„´precedence_heuristic §cell_idÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542b´downstream_cells_map„¢i0“Ù$e57539a7-d8fb-413d-be9e-d2459ed65610Ù$2604b66d-2c44-44b9-837c-9894f104adfcÙ$3710d552-729f-4e41-9da2-1756907c4ced¡V“Ù$e57539a7-d8fb-413d-be9e-d2459ed65610Ù$2604b66d-2c44-44b9-837c-9894f104adfcÙ$3710d552-729f-4e41-9da2-1756907c4ced¡R“Ù$e57539a7-d8fb-413d-be9e-d2459ed65610Ù$2604b66d-2c44-44b9-837c-9894f104adfcÙ$3710d552-729f-4e41-9da2-1756907c4ced¢v0“Ù$e57539a7-d8fb-413d-be9e-d2459ed65610Ù$2604b66d-2c44-44b9-837c-9894f104adfcÙ$3710d552-729f-4e41-9da2-1756907c4ced²upstream_cells_map€Ù$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfc„´precedence_heuristic §cell_idÙ$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfc´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$f01345c5-3b96-40f1-8ed3-0fbe85f908d9„´precedence_heuristic §cell_idÙ$f01345c5-3b96-40f1-8ed3-0fbe85f908d9´downstream_cells_map¡N‘Ù$990863df-8549-434a-acb0-22207a4df287²upstream_cells_map‹§@md_str¤Core«PlutoRunner·PlutoRunner.create_bond¯Core.applicable¨getindex¡:¨Base.get¥@bind¦Slider¤BaseÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474f„´precedence_heuristic §cell_idÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474f´downstream_cells_map€²upstream_cells_map„¡v‘Ù$f8bf0e47-0089-4553-8604-cd8347345658¬Differential²expand_derivativesª@variablesÙ$4e2edbda-28ae-4978-a94a-1d23766d4937„´precedence_heuristic §cell_idÙ$4e2edbda-28ae-4978-a94a-1d23766d4937´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$d55c983f-16bb-484a-9c2f-80b8e3b010b8„´precedence_heuristic §cell_idÙ$d55c983f-16bb-484a-9c2f-80b8e3b010b8´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$c736d68f-95f1-47c6-bd75-13d62a895e12„´precedence_heuristic §cell_idÙ$c736d68f-95f1-47c6-bd75-13d62a895e12´downstream_cells_map€²upstream_cells_map‚£eps§Float64Ù$3e4cf748-d198-4745-9d8b-5d3bd8c618aa„´precedence_heuristic §cell_idÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aa´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$349d6db7-2b93-4833-ac0a-c0c398133814„´precedence_heuristic §cell_idÙ$349d6db7-2b93-4833-ac0a-c0c398133814´downstream_cells_map€²upstream_cells_map‚¡+¢==Ù$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076„´precedence_heuristic §cell_idÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076´downstream_cells_map¨h_values’Ù$dbe26026-6f55-4664-a4f6-77f30eb225deÙ$cc19d720-ce62-469e-9323-12a79c4081e1²upstream_cells_map‚¡:¡^Ù$e21c528a-bc5e-448a-922f-97fc029a37eb„´precedence_heuristic §cell_idÙ$e21c528a-bc5e-448a-922f-97fc029a37eb´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$06a18358-597b-4532-a735-5031a544c034„´precedence_heuristic §cell_idÙ$06a18358-597b-4532-a735-5031a544c034´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$dbe26026-6f55-4664-a4f6-77f30eb225de„´precedence_heuristic §cell_idÙ$dbe26026-6f55-4664-a4f6-77f30eb225de´downstream_cells_map«derivatives‘Ù$eacbce03-d987-4d20-bc56-815c4f5f4907²upstream_cells_map†¡v‘Ù$f8bf0e47-0089-4553-8604-cd8347345658¢t0‘Ù$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6¡-¡/¡+¨h_values‘Ù$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076Ù$06867a4c-c4b0-47a5-9678-22baab9ca83f„´precedence_heuristic §cell_idÙ$06867a4c-c4b0-47a5-9678-22baab9ca83f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaaf„´precedence_heuristic §cell_idÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaaf´downstream_cells_map€²upstream_cells_map„§@printf¡:¤glog‘Ù$2604b66d-2c44-44b9-837c-9894f104adfc¦stdoutÙ$f4a47680-4ab6-4d51-80da-1cdecc53cde2„´precedence_heuristic §cell_idÙ$f4a47680-4ab6-4d51-80da-1cdecc53cde2´downstream_cells_map€²upstream_cells_map³RobustLocalResourceÙ$e57539a7-d8fb-413d-be9e-d2459ed65610„´precedence_heuristic §cell_idÙ$e57539a7-d8fb-413d-be9e-d2459ed65610´downstream_cells_map€²upstream_cells_map†§@md_str¢v0‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¢i0‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¡V‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¡R‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¨getindexÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0„´precedence_heuristic §cell_idÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66„´precedence_heuristic §cell_idÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209„´precedence_heuristic §cell_idÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$dbbedfb0-f011-431c-8302-9e46a8ad32ff„´precedence_heuristic §cell_idÙ$dbbedfb0-f011-431c-8302-9e46a8ad32ff´downstream_cells_map€²upstream_cells_mapŠ¦xlims!¤zero¡:¡-¥sort!§scatter¡^§append!¡*¦vline!Ù$41eb08d1-14c8-4d04-9216-aec0304581be„´precedence_heuristic §cell_idÙ$41eb08d1-14c8-4d04-9216-aec0304581be´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9f„´precedence_heuristic §cell_idÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$51ba2f16-d610-401c-a1d8-6af94dbbdd09„´precedence_heuristic §cell_idÙ$51ba2f16-d610-401c-a1d8-6af94dbbdd09´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$7b74843b-1198-40fb-a89f-9dd86738c2cd„´precedence_heuristic §cell_idÙ$7b74843b-1198-40fb-a89f-9dd86738c2cd´downstream_cells_map¤data‘Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458²upstream_cells_map€Ù$cfc885de-9dd9-4008-9124-fbd31a799535„´precedence_heuristic §cell_idÙ$cfc885de-9dd9-4008-9124-fbd31a799535´downstream_cells_map€²upstream_cells_map‚¡v‘Ù$f8bf0e47-0089-4553-8604-cd8347345658¤plotÙ$f8bf0e47-0089-4553-8604-cd8347345658„´precedence_heuristic §cell_idÙ$f8bf0e47-0089-4553-8604-cd8347345658´downstream_cells_map¡v”Ù$cfc885de-9dd9-4008-9124-fbd31a799535Ù$2dad6ffd-92a2-4b60-9e33-ea978dba474fÙ$dbe26026-6f55-4664-a4f6-77f30eb225deÙ$eacbce03-d987-4d20-bc56-815c4f5f4907²upstream_cells_map„¡-¡^¡+¡*Ù$2604b66d-2c44-44b9-837c-9894f104adfc„´precedence_heuristic §cell_idÙ$2604b66d-2c44-44b9-837c-9894f104adfc´downstream_cells_map¤glog‘Ù$9a8dae54-d4ea-47bf-8f77-54286cedcaaf²upstream_cells_map‰¢i0‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¡-£log¡/¡V‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¡+¡*¡R‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¢v0‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542bÙ$67e61788-2000-4fe4-8a14-48faa2df5bbd„´precedence_heuristic §cell_idÙ$67e61788-2000-4fe4-8a14-48faa2df5bbd´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$76721956-b2e1-4b33-b5f3-fca94b4a89b2„´precedence_heuristic §cell_idÙ$76721956-b2e1-4b33-b5f3-fca94b4a89b2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$be44b23a-fd7f-4536-96c0-cd1c7326294d„´precedence_heuristic §cell_idÙ$be44b23a-fd7f-4536-96c0-cd1c7326294d´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$75610334-8c66-4ef8-b108-68cdaa189721„´precedence_heuristic §cell_idÙ$75610334-8c66-4ef8-b108-68cdaa189721´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$ba227f1d-542a-4d9b-adad-5e17755f3c30„´precedence_heuristic §cell_idÙ$ba227f1d-542a-4d9b-adad-5e17755f3c30´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$357aa8d2-9e50-48a2-8467-faf8c2ed90ad„´precedence_heuristic §cell_idÙ$357aa8d2-9e50-48a2-8467-faf8c2ed90ad´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$848c7983-711a-44e5-939b-a705fd400ffa„´precedence_heuristic §cell_idÙ$848c7983-711a-44e5-939b-a705fd400ffa´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21„´precedence_heuristic §cell_idÙ$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7„´precedence_heuristic §cell_idÙ$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897„´precedence_heuristic §cell_idÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$cc19d720-ce62-469e-9323-12a79c4081e1„´precedence_heuristic §cell_idÙ$cc19d720-ce62-469e-9323-12a79c4081e1´downstream_cells_map€²upstream_cells_map†¢t0‘Ù$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6¡:¦errors‘Ù$eacbce03-d987-4d20-bc56-815c4f5f4907¤plot¡^¨h_values‘Ù$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458„´precedence_heuristic §cell_idÙ$06084cb6-0d9c-46eb-adb7-38b3b607d458´downstream_cells_mapƒ¥lines¤rate‘Ù$990863df-8549-434a-acb0-22207a4df287«temperature‘Ù$990863df-8549-434a-acb0-22207a4df287²upstream_cells_map‹¸LaTeXStrings.latexstring¤data‘Ù$7b74843b-1198-40fb-a89f-9dd86738c2cd§Float64¥parse§scatter¬LaTeXStrings‘Ù$c9aac823-6556-4a98-92e4-7e8631e7b71e¥split¡:¦@L_str£end¡-Ù$1dbb2e84-efb4-41b7-a31d-fc349c448a32„´precedence_heuristic §cell_idÙ$1dbb2e84-efb4-41b7-a31d-fc349c448a32´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2„´precedence_heuristic §cell_idÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$d0257ff3-6873-44df-886d-0236f0b729ea„´precedence_heuristic §cell_idÙ$d0257ff3-6873-44df-886d-0236f0b729ea´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$c9aac823-6556-4a98-92e4-7e8631e7b71e„´precedence_heuristic§cell_idÙ$c9aac823-6556-4a98-92e4-7e8631e7b71e´downstream_cells_mapˆ§NLsolve©Symbolics§PlutoUI¥Plots°HypertextLiteral‘Ù$ac1a0435-6447-45fc-97b6-475e8586eebd¦Printf¬LaTeXStrings’Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458Ù$990863df-8549-434a-acb0-22207a4df287²PlutoTeachingTools²upstream_cells_map€Ù$c07c1593-bfa1-44ea-8320-aa20b259a0cf„´precedence_heuristic §cell_idÙ$c07c1593-bfa1-44ea-8320-aa20b259a0cf´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$459361fa-2abd-49ec-aa88-8e37e679c782„´precedence_heuristic §cell_idÙ$459361fa-2abd-49ec-aa88-8e37e679c782´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$a089a707-ff05-4bdb-bd31-1422617388fc„´precedence_heuristic §cell_idÙ$a089a707-ff05-4bdb-bd31-1422617388fc´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$a6c77495-b336-40b2-afaf-184d96b4dce9„´precedence_heuristic §cell_idÙ$a6c77495-b336-40b2-afaf-184d96b4dce9´downstream_cells_map€²upstream_cells_map„§@printf¡:¤gexp‘Ù$3710d552-729f-4e41-9da2-1756907c4ced¦stdoutÙ$079e9f17-27a2-4284-b283-09e6aadbc53b„´precedence_heuristic §cell_idÙ$079e9f17-27a2-4284-b283-09e6aadbc53b´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcf„´precedence_heuristic §cell_idÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcf´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$2255ea65-76a7-403b-af0a-d9dd489b105c„´precedence_heuristic §cell_idÙ$2255ea65-76a7-403b-af0a-d9dd489b105c´downstream_cells_map€²upstream_cells_mapƒ§@md_str¢t0‘Ù$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6¨getindexÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80d„´precedence_heuristic §cell_idÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80d´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$b192ec68-836c-4fb0-8f03-6ebb01cfcf68„´precedence_heuristic §cell_idÙ$b192ec68-836c-4fb0-8f03-6ebb01cfcf68´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$71c91579-a894-44b5-b4d7-f8d98667b977„´precedence_heuristic §cell_idÙ$71c91579-a894-44b5-b4d7-f8d98667b977´downstream_cells_map€²upstream_cells_map¯TableOfContentsÙ$5a609e3e-ed94-4e4e-b9e4-c70fd459a25c„´precedence_heuristic §cell_idÙ$5a609e3e-ed94-4e4e-b9e4-c70fd459a25c´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3„´precedence_heuristic §cell_idÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3´downstream_cells_map‚¡t¡h²upstream_cells_mapƒ¡-¡/¡+Ù$ae449fa8-76c9-4d1d-af05-464692436727„´precedence_heuristic §cell_idÙ$ae449fa8-76c9-4d1d-af05-464692436727´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$3710d552-729f-4e41-9da2-1756907c4ced„´precedence_heuristic §cell_idÙ$3710d552-729f-4e41-9da2-1756907c4ced´downstream_cells_map¤gexp‘Ù$a6c77495-b336-40b2-afaf-184d96b4dce9²upstream_cells_mapˆ£exp¢i0‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¡-¡/¡V‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¡*¡R‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542b¢v0‘Ù$7047b5e6-24df-4d22-b4ca-e2872ecb542bÙ$7d265705-3ef0-4974-bfcc-ee25707dee1e„´precedence_heuristic §cell_idÙ$7d265705-3ef0-4974-bfcc-ee25707dee1e´downstream_cells_map€²upstream_cells_map‚¡+¢==Ù$eacbce03-d987-4d20-bc56-815c4f5f4907„´precedence_heuristic§cell_idÙ$eacbce03-d987-4d20-bc56-815c4f5f4907´downstream_cells_mapƒ¦errors‘Ù$cc19d720-ce62-469e-9323-12a79c4081e1«ForwardDiff‘Ù$eacbce03-d987-4d20-bc56-815c4f5f4907©reference²upstream_cells_map‡¡v‘Ù$f8bf0e47-0089-4553-8604-cd8347345658¢t0‘Ù$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6«ForwardDiff‘Ù$eacbce03-d987-4d20-bc56-815c4f5f4907¡-¶ForwardDiff.derivative«derivatives‘Ù$dbe26026-6f55-4664-a4f6-77f30eb225de£absÙ$ac1a0435-6447-45fc-97b6-475e8586eebd„´precedence_heuristic §cell_idÙ$ac1a0435-6447-45fc-97b6-475e8586eebd´downstream_cells_map€²upstream_cells_map‡³RobustLocalResourceÙ HypertextLiteral.attribute_value·HypertextLiteral.Bypass·HypertextLiteral.Result°HypertextLiteral‘Ù$c9aac823-6556-4a98-92e4-7e8631e7b71e¸HypertextLiteral.content¤@htlÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31a„´precedence_heuristic §cell_idÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31a´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6„´precedence_heuristic §cell_idÙ$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6´downstream_cells_map¢t0”Ù$2255ea65-76a7-403b-af0a-d9dd489b105cÙ$dbe26026-6f55-4664-a4f6-77f30eb225deÙ$eacbce03-d987-4d20-bc56-815c4f5f4907Ù$cc19d720-ce62-469e-9323-12a79c4081e1²upstream_cells_map‹§@md_str¤Core«PlutoRunner·PlutoRunner.create_bond¯Core.applicable¨getindex¡:¨Base.get¥@bind¦Slider¤Base´cell_execution_orderÜEÙ$c9aac823-6556-4a98-92e4-7e8631e7b71eÙ$67e61788-2000-4fe4-8a14-48faa2df5bbdÙ$71c91579-a894-44b5-b4d7-f8d98667b977Ù$a089a707-ff05-4bdb-bd31-1422617388fcÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3Ù$1dbb2e84-efb4-41b7-a31d-fc349c448a32Ù$b192ec68-836c-4fb0-8f03-6ebb01cfcf68Ù$5a609e3e-ed94-4e4e-b9e4-c70fd459a25cÙ$f8bf0e47-0089-4553-8604-cd8347345658Ù$4e2edbda-28ae-4978-a94a-1d23766d4937Ù$cfc885de-9dd9-4008-9124-fbd31a799535Ù$d0257ff3-6873-44df-886d-0236f0b729eaÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474fÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076Ù$be44b23a-fd7f-4536-96c0-cd1c7326294dÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0Ù$51ba2f16-d610-401c-a1d8-6af94dbbdd09Ù$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21Ù$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6Ù$2255ea65-76a7-403b-af0a-d9dd489b105cÙ$dbe26026-6f55-4664-a4f6-77f30eb225deÙ$eacbce03-d987-4d20-bc56-815c4f5f4907Ù$cc19d720-ce62-469e-9323-12a79c4081e1Ù$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7Ù$357aa8d2-9e50-48a2-8467-faf8c2ed90adÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80dÙ$41eb08d1-14c8-4d04-9216-aec0304581beÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3Ù$75610334-8c66-4ef8-b108-68cdaa189721Ù$7d265705-3ef0-4974-bfcc-ee25707dee1eÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2Ù$079e9f17-27a2-4284-b283-09e6aadbc53bÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2Ù$dbbedfb0-f011-431c-8302-9e46a8ad32ffÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897Ù$d55c983f-16bb-484a-9c2f-80b8e3b010b8Ù$c736d68f-95f1-47c6-bd75-13d62a895e12Ù$e21c528a-bc5e-448a-922f-97fc029a37ebÙ$349d6db7-2b93-4833-ac0a-c0c398133814Ù$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfcÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aaÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66Ù$c07c1593-bfa1-44ea-8320-aa20b259a0cfÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209Ù$f4a47680-4ab6-4d51-80da-1cdecc53cde2Ù$ed573aed-09e2-47ff-8b91-fdd14f3bee0fÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9fÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542bÙ$848c7983-711a-44e5-939b-a705fd400ffaÙ$e57539a7-d8fb-413d-be9e-d2459ed65610Ù$2604b66d-2c44-44b9-837c-9894f104adfcÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2Ù$9a8dae54-d4ea-47bf-8f77-54286cedcaafÙ$459361fa-2abd-49ec-aa88-8e37e679c782Ù$76721956-b2e1-4b33-b5f3-fca94b4a89b2Ù$3710d552-729f-4e41-9da2-1756907c4cedÙ$a6c77495-b336-40b2-afaf-184d96b4dce9Ù$06867a4c-c4b0-47a5-9678-22baab9ca83fÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31aÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcfÙ$86590ede-19cd-4610-baa4-eb3f1286bd67Ù$ba227f1d-542a-4d9b-adad-5e17755f3c30Ù$7b74843b-1198-40fb-a89f-9dd86738c2cdÙ$06a18358-597b-4532-a735-5031a544c034Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458Ù$f01345c5-3b96-40f1-8ed3-0fbe85f908d9Ù$990863df-8549-434a-acb0-22207a4df287Ù$ae449fa8-76c9-4d1d-af05-464692436727Ù$ac1a0435-6447-45fc-97b6-475e8586eebd´last_hot_reload_timeË®process_status¥ready¤pathÙN/home/runner/work/numerical-analysis/numerical-analysis/src/01_Introduction.jl­pluto_version¨v0.20.24ªcell_orderÜEÙ$67e61788-2000-4fe4-8a14-48faa2df5bbdÙ$c9aac823-6556-4a98-92e4-7e8631e7b71eÙ$71c91579-a894-44b5-b4d7-f8d98667b977Ù$a089a707-ff05-4bdb-bd31-1422617388fcÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3Ù$1dbb2e84-efb4-41b7-a31d-fc349c448a32Ù$b192ec68-836c-4fb0-8f03-6ebb01cfcf68Ù$5a609e3e-ed94-4e4e-b9e4-c70fd459a25cÙ$f8bf0e47-0089-4553-8604-cd8347345658Ù$4e2edbda-28ae-4978-a94a-1d23766d4937Ù$cfc885de-9dd9-4008-9124-fbd31a799535Ù$d0257ff3-6873-44df-886d-0236f0b729eaÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474fÙ$2255ea65-76a7-403b-af0a-d9dd489b105cÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076Ù$be44b23a-fd7f-4536-96c0-cd1c7326294dÙ$dbe26026-6f55-4664-a4f6-77f30eb225deÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0Ù$eacbce03-d987-4d20-bc56-815c4f5f4907Ù$51ba2f16-d610-401c-a1d8-6af94dbbdd09Ù$cc19d720-ce62-469e-9323-12a79c4081e1Ù$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21Ù$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6Ù$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7Ù$357aa8d2-9e50-48a2-8467-faf8c2ed90adÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80dÙ$41eb08d1-14c8-4d04-9216-aec0304581beÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3Ù$75610334-8c66-4ef8-b108-68cdaa189721Ù$7d265705-3ef0-4974-bfcc-ee25707dee1eÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2Ù$079e9f17-27a2-4284-b283-09e6aadbc53bÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2Ù$dbbedfb0-f011-431c-8302-9e46a8ad32ffÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897Ù$d55c983f-16bb-484a-9c2f-80b8e3b010b8Ù$c736d68f-95f1-47c6-bd75-13d62a895e12Ù$e21c528a-bc5e-448a-922f-97fc029a37ebÙ$349d6db7-2b93-4833-ac0a-c0c398133814Ù$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfcÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aaÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66Ù$c07c1593-bfa1-44ea-8320-aa20b259a0cfÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209Ù$f4a47680-4ab6-4d51-80da-1cdecc53cde2Ù$ed573aed-09e2-47ff-8b91-fdd14f3bee0fÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9fÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542bÙ$848c7983-711a-44e5-939b-a705fd400ffaÙ$e57539a7-d8fb-413d-be9e-d2459ed65610Ù$2604b66d-2c44-44b9-837c-9894f104adfcÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2Ù$9a8dae54-d4ea-47bf-8f77-54286cedcaafÙ$459361fa-2abd-49ec-aa88-8e37e679c782Ù$76721956-b2e1-4b33-b5f3-fca94b4a89b2Ù$3710d552-729f-4e41-9da2-1756907c4cedÙ$a6c77495-b336-40b2-afaf-184d96b4dce9Ù$06867a4c-c4b0-47a5-9678-22baab9ca83fÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31aÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcfÙ$86590ede-19cd-4610-baa4-eb3f1286bd67Ù$ba227f1d-542a-4d9b-adad-5e17755f3c30Ù$7b74843b-1198-40fb-a89f-9dd86738c2cdÙ$06a18358-597b-4532-a735-5031a544c034Ù$06084cb6-0d9c-46eb-adb7-38b3b607d458Ù$f01345c5-3b96-40f1-8ed3-0fbe85f908d9Ù$990863df-8549-434a-acb0-22207a4df287Ù$ae449fa8-76c9-4d1d-af05-464692436727Ù$ac1a0435-6447-45fc-97b6-475e8586eebd±published_objects€¥nbpkgŠ¶waiting_for_permissionÂÙ,waiting_for_permission_but_probably_disabled²installed_versionsŠ«ForwardDiff¥1.3.1§NLsolve¥4.5.1©Symbolics¥7.8.0§PlutoUI¦0.7.79¥Plots¦1.41.4°HypertextLiteral¥1.0.0«Polynomials¥4.1.0¬LaTeXStrings¥1.4.0¦Printf¦stdlib²PlutoTeachingTools¥0.4.7°terminal_outputs‹«ForwardDiffÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... §PlutoUIÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... ²PlutoTeachingToolsÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... ©SymbolicsÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... ¬LaTeXStringsÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... ¥PlotsÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... «PolynomialsÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... §NLsolveÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... ªnbpkg_syncÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... °HypertextLiteralÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... ¦PrintfÚ Resolving... ===  Installed NLSolversBase ───────────── v7.10.0  Installed LineSearches ────────────── v7.5.1  Installed DifferentiationInterface ── v0.7.14  Installed RuntimeGeneratedFunctions ─ v0.5.16  Installed FiniteDiff ──────────────── v2.29.0  Installed Symbolics ───────────────── v7.8.0  Installed SymbolicUtils ───────────── v4.13.1  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_qxriioceqx/Manifest.toml` [a65dc6b1] + Xorg_libpciaccess_jll v0.18.1+0 [8e53e030] + libdrm_jll v2.4.125+1 [9a156e7d] + libva_jll v2.23.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation... §enabledìinstantiated÷restart_recommended_msgÀ´restart_required_msgÀ¯install_time_nsÏ:§¡¨Õ­busy_packages«cell_inputsÞEÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2„§cell_idÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2¤codeÚmd""" The **set of floating-point numbers** has elements of the form ```math y = \pm m \, \beta^{e-t}. ``` It is thus characterised by four integer parameters: - the **base** (or radix) $\beta$. Almost always binary, i.e. $β = 2$, - the **number of significand digits** $t$ and - the **exponent range** $e_\text{min} \leq e \leq e_\text{max}$. In the definition of $y$ the integer $m$ is the **significand** (or mantissa), which has $t$ number of digits, i.e. $m = (a_1 a_2 \cdots a_t)$, which satisfy $0 < a_1 \leq β-1$ and $0 ≤ a_i ≤ β-1$ for $i=2,\ldots,t$. The most common case are **double-precision floating-point numbers** with $β=2$, $t = 24$, $e_\text{min} = -1023$ and $e_\text{max} = +1022$. This is unfortunately too many numbers to illustrate easily. To still get a visual representation of the "denseness" of floating-point numbers, we therefore consider a toy case with $\beta = 2$, $t = 3$, $e_\text{min} = -1$ and $e_\text{max} = 3$. Considering only the positive numbers, the following numbers can be represented: """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2„§cell_idÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2¤codeÙ3md""" which explains the zero result we obtain. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3„§cell_idÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3¤codeÚÉmd""" ## How this course works Context of the course: - In this lecture we focus very much on **teaching you the high-level ideas** of key numerical algorithms. We keep proofs to a minimal level, where they are easy or help understanding, but **not all technicalities can be avoided**. - The **role of this lecture** in the study curriculum is to **provide a broad overview of many numerical techniques**, which you will need in future classes. Unfortunately in this lecture **we have little time to go into more interesting applications**. While we do employ examples to motivate our mathematical study, these examples therefore can appear constructed or only loosely connected to the rest of your studies. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$990863df-8549-434a-acb0-22207a4df287„§cell_idÙ$990863df-8549-434a-acb0-22207a4df287¤codeÚ let using Polynomials # Package for fitting polynomials (and more ...) polynomial = Polynomials.fit(temperature, rate, N) p = plot(polynomial, label="Polynomial fit", lw=2, xlim=(245, 355), legend=:bottomright, ylim=(1.25, 2.3)) scatter!(p, temperature, rate, label="Observed rates") scatter!(p, [255], [polynomial(255.0)]; label=L"Prediction $f(298 K)$") vline!(p, [255], label="", ls=:dash, lw=2, c=3) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$ed573aed-09e2-47ff-8b91-fdd14f3bee0f„§cell_idÙ$ed573aed-09e2-47ff-8b91-fdd14f3bee0f¤codeÚbmd""" which consists of - Some voltage source, generating a voltage $V$ - A resistor $R$ with the linear relationship ```math v_R = R \, i ``` between the current $i$ and its voltage $v_R$. - A diode for which we will take the standard [Shockley diode model](https://en.wikipedia.org/wiki/Diode_modelling), i.e. the equation ```math i = i_0 (e^{v_D / v_0} - 1) ``` between the diode's current $i$ and voltage $v_D$. $v_0$ and $i_0$ are parameters, which characterise the diode. - According to the circuit laws, the voltages across the circuit elements need to sum, i.e. $V = v_D + v_R$. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$86590ede-19cd-4610-baa4-eb3f1286bd67„§cell_idÙ$86590ede-19cd-4610-baa4-eb3f1286bd67¤codeÚmd""" Even if you now might think, that your heart beats for **experimental research** and you will never need numerics, keep in mind that **all data analysis** uses procedures **based on such techniques**. **Even commercial packages** for experimental post-processing rely heavily on the procedures we will cover and **sometimes get it wrong**. See for example this [report on Microsoft Excel](https://www.economist.com/graphic-detail/2016/09/07/excel-errors-and-science-papers)). This **can and has compromised scientific fundings in the past**. Therefore it's **best to be prepared**, so you can judge what is wrong: The experiment or the numerics. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542b„§cell_idÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542b¤codeÙ0begin i0 = 1.0 v0 = 0.1 R = 1.0 V = 1.0 end;¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfc„§cell_idÙ$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfc¤codeÙfmd"namely because $10^{-16}$ is *smaller* than the machine epsilon, such that $fl(1 + 10^{-16}) = 1$."¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$f01345c5-3b96-40f1-8ed3-0fbe85f908d9„§cell_idÙ$f01345c5-3b96-40f1-8ed3-0fbe85f908d9¤codeÚ{md""" Still, it seems reasonable that we should be able to **determine some continuous function** $f$ **from the observed data**, which **establishes a good model** for the relationship $k = f(T)$. Albeit $255 K$ has not been measured, we can thus evaluate $f(255 K)$ and get an estimate for the rate at this temperature. Since the new temperature $255 K$ islocated *within* the observed data range (i.e. here $250K$ to $350K$) we call this procedure **interpolation**. In this lecture we will discuss some common interpolation techniques. In particular we will develop the **mathematical formalism** for these techniques and --- most importantly --- we will use this formalism to understand conditions when these methods work and **when these methods fail**. In fact our example here is already a little tricky. Let us illustrate this point for **polynomial interpolation**, one particularly frequent technique. Without going into details for now, one basic idea is to fit a polynomial of degree $N$ ```math k(T) = \sum_{n=1}^{N} α_n T^n ``` to the data. By some procedure discussed later we thus determine the unknown polynomial coefficients $α_n$, such that the polynomial best matches our observations and use that to determine $f(255 K)$. Let's see the result of such a fit. The slider let's you play with the polynomial order: - `N = `$(@bind N Slider(1:10; show_value=true, default=1)) """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474f„§cell_idÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474f¤codeÙ¦let @variables t # Define a variable dt = Differential(t) # Differentiating wrt. t dv_dt = dt( v(t) ) # Compute dv / dt expand_derivatives(dv_dt) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$4e2edbda-28ae-4978-a94a-1d23766d4937„§cell_idÙ$4e2edbda-28ae-4978-a94a-1d23766d4937¤codeÙ$md" We can plot it to get an idea: "¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$d55c983f-16bb-484a-9c2f-80b8e3b010b8„§cell_idÙ$d55c983f-16bb-484a-9c2f-80b8e3b010b8¤codeÙFmd""" For double-precision numbers we have for the machine epsilon """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$c736d68f-95f1-47c6-bd75-13d62a895e12„§cell_idÙ$c736d68f-95f1-47c6-bd75-13d62a895e12¤code¬eps(Float64)¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aa„§cell_idÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aa¤codeÚ“md""" !!! info "Takeaway: Properties of double-precision numbers" For standard double-precision floating-point numbers (`Float64`) we have $ε_M ≈ 2 \cdot 10^{-16}$, such that floating-point operations are accurate to a **relative error** of $\frac{ε_M}{2} ≈ 10^{-16}$. *Tip:* This is the only information you need to remember about the structure of floating-point numbers for this class. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$349d6db7-2b93-4833-ac0a-c0c398133814„§cell_idÙ$349d6db7-2b93-4833-ac0a-c0c398133814¤code®1 + 1e-16 == 1¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076„§cell_idÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076¤code¼h_values = 10 .^ (-15:0.5:1)¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$e21c528a-bc5e-448a-922f-97fc029a37eb„§cell_idÙ$e21c528a-bc5e-448a-922f-97fc029a37eb¤codeÙ!md""" which finally explains """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$06a18358-597b-4532-a735-5031a544c034„§cell_idÙ$06a18358-597b-4532-a735-5031a544c034¤codeÚ-md"""Now we are curious about the rates at another temperature, say $255 K$. The basic laws of thermodynamics and chemical kinetics tell us that the rate should be a *continuous function* of the temperature. For example [Arrhenius' law](https://en.wikipedia.org/wiki/Arrhenius_equation) ```math \tag{4} k(T) = A \exp\left( - \frac{E_A}{k_B T} \right) ``` establishes such a relationship, where $A$, $E_A$ and $k_B$ are some constants. Note, that in this case the behaviour is more complicated as is immediately obvious from a plot of the observed data: """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$dbe26026-6f55-4664-a4f6-77f30eb225de„§cell_idÙ$dbe26026-6f55-4664-a4f6-77f30eb225de¤codeÙ;derivatives = [ ( v(t0 + h) - v(t0) )/h for h in h_values ]¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$06867a4c-c4b0-47a5-9678-22baab9ca83f„§cell_idÙ$06867a4c-c4b0-47a5-9678-22baab9ca83f¤codeÙÚmd""" Even though the **method 2 seems equally plausible as method 1** on first sight, **method 2 does not converge**. As a result this method **is not helpful to us to obtain the fixed point / the diode voltage**. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaaf„§cell_idÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaaf¤codeÙlet vD = 0.1 for i in 1:10 vD = glog(vD) # Call fixed-point map @printf "iter %2i: vD = %.15f\n" i vD # Print formatted data end end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$f4a47680-4ab6-4d51-80da-1cdecc53cde2„§cell_idÙ$f4a47680-4ab6-4d51-80da-1cdecc53cde2¤codeÙ©RobustLocalResource("https://raw.githubusercontent.com/epfl-matmat/numerical-analysis/09d365542432dc652a9ed1ce5c5f54075590aebd/notes/img/circuit.png", "img/circuit.png")¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$e57539a7-d8fb-413d-be9e-d2459ed65610„§cell_idÙ$e57539a7-d8fb-413d-be9e-d2459ed65610¤codeÚmd""" Note that, since $f$ is not just a simple polynomial, but a **non-linear function** there is no explicit analytic formula for finding its solution. We therefore need to consider iterative approaches. Interestingly enough in this case simple repeated iteration, i.e. ```math v^{(k+1)}_D = g_\text{log}(v^{(k)}_D) \qquad \text{for $k = 1, 2, \ldots$}, ``` just works to find the fixed point. To see that we select the parameters * `i0 =` $(i0) * `v0 =` $(v0) * `R =` $(R) * `V =` $(V) and define the fixed-point map """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0„§cell_idÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0¤codeÙ8md"... and compute the error against a reference value:"¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66„§cell_idÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66¤codeÚòmd""" !!! danger "Errors in algorithms can be much larger than machine epsilon" ust because the relative error of an individual floating-point operation is bounded by $\frac{ε_M}{2}$, this **does not imply that the error of an algorithm is bounded** by this value. This is exactly what we saw in the numerical differentiation example above, where the observed error in the computed derivative amounts to values well beyond $\frac{ε_M}{2}$, such that all accuracy in the final answer is lost. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209„§cell_idÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209¤codeÚ md""" ## Fixed-point problems The previous discussion was mostly centred around the *accuracy* of a computation. In this example we will get some first idea about the challenges when designing a good numerical algorithm. We consider the simple Diode model circuit """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$dbbedfb0-f011-431c-8302-9e46a8ad32ff„§cell_idÙ$dbbedfb0-f011-431c-8302-9e46a8ad32ff¤codeÚalet β = 2.0 t = 3 emin = -1 emax = 3 numbers = [0.0] append!(numbers, [m * β^(e - t) for m in β^(t-1):(β^t-1) for e in emin:emax]) sort!(numbers) p = scatter(numbers, zero(numbers); label="Representable numbers", mark=:x, ylims=(-1, 1), ms=6) vline!(p, [0.25, 0.5, 1, 2, 4], label="Factors of 2", c=3) xlims!(p, (-0.01 * 8, 8)) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$41eb08d1-14c8-4d04-9216-aec0304581be„§cell_idÙ$41eb08d1-14c8-4d04-9216-aec0304581be¤codeÚ(md""" Let us disect one particular example in detail. We consider $v(t) = t$, where one computes ```math \frac{v(t+h) - v(t)}{h} = \frac{(t+h)-t}{h}, ``` which is clearly equal to $1$ independent of the choice of $h$. However, computing this expression numerically for $h=10^{-16}$ we observe """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9f„§cell_idÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9f¤codeÚVmd""" We now want to solve this problem numerically, that is **find the Diode voltage $v_D$** and the **current $i$** from the parameters $R$, $V$, $i_0$ and $v_0$. If you have never encountered circuit theory, just take it for granted that we now have a problem consisting of the three equations ```math \begin{align} \tag{2a} V &= v_D + v_R \\ \tag{2b} v_R &= R\, i \\ \tag{2c} i &= i_0 (e^{v_D / v_0} - 1) \end{align} ``` where $v_D$ is the unknown we want to determine. Our goal is to model this circuit, i.e. understand the current $i$ and its voltage $v_D$ across the circuit elements. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$51ba2f16-d610-401c-a1d8-6af94dbbdd09„§cell_idÙ$51ba2f16-d610-401c-a1d8-6af94dbbdd09¤codeÙ1md"Finally we plot the errors on a log-log plot:"¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$7b74843b-1198-40fb-a89f-9dd86738c2cd„§cell_idÙ$7b74843b-1198-40fb-a89f-9dd86738c2cd¤codeÚIdata = """ # Temperature(K) Rate(1/s) 250.0 1.51756 260.0 1.59566 270.0 1.67888 280.0 1.78110 290.0 1.95476 300.0 2.20728 310.0 2.08967 320.0 2.03635 330.0 2.05474 340.0 2.09338 350.0 2.13819 """;¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$cfc885de-9dd9-4008-9124-fbd31a799535„§cell_idÙ$cfc885de-9dd9-4008-9124-fbd31a799535¤codeÙìlet p = plot(v; ylims=(-10, 2), # Limit on y axis xlims=(-0.5, 1.5), # Limit on x axis linewidth=2, # Width of the blue line label="Velocity", # Label of the graph xlabel="t", ylabel="v") end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$f8bf0e47-0089-4553-8604-cd8347345658„§cell_idÙ$f8bf0e47-0089-4553-8604-cd8347345658¤codeÙ;v(t) = 64t * (1 − t) * (1 − 2t)^2 * (1 − 8t + 8t^2)^2¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$2604b66d-2c44-44b9-837c-9894f104adfc„§cell_idÙ$2604b66d-2c44-44b9-837c-9894f104adfc¤codeÙ8function glog(vD) v0 * log((V - vD) / (R * i0) + 1) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$67e61788-2000-4fe4-8a14-48faa2df5bbd„§cell_idÙ$67e61788-2000-4fe4-8a14-48faa2df5bbd¤codeÙƒmd""" !!! info "" [Click here to view the PDF version.](https://teaching.matmat.org/numerical-analysis/01_Introduction.pdf) """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$76721956-b2e1-4b33-b5f3-fca94b4a89b2„§cell_idÙ$76721956-b2e1-4b33-b5f3-fca94b4a89b2¤codeÚ^md""" #### Method 2 Now the arguments to introduce Method 1 were in fact a little convoluted. Let's try to directly balance the voltage across the circuit, i.e. directly employ $V = v_R + v_D$. Then using equations (2a) to (2c) this leads to: ```math \tag{5} V = v_R + v_D = R\, i + v_D = R \, i_0 \left( e^{v_D/v_0} - 1 \right) + v_D ``` or ```math V - R \, i_0 \left( e^{v_D/v_0} - 1 \right) = v_D ``` Introducing a function ```math \tag{6} g_\text{exp}(x) = V - R \, i_0 \left( e^{x/v_0} - 1 \right). ``` we again observe a fixed-point problem $g_\text{exp}(v_D) = v_D$. We again iterate as before: """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$be44b23a-fd7f-4536-96c0-cd1c7326294d„§cell_idÙ$be44b23a-fd7f-4536-96c0-cd1c7326294d¤codeÙ8md"We compute the derivatives at each value for $h$ ..."¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$75610334-8c66-4ef8-b108-68cdaa189721„§cell_idÙ$75610334-8c66-4ef8-b108-68cdaa189721¤codeÚgmd"""which is clearly wrong. We are faced with this error because the **representation of numbers on a computer has only finite precision**. In fact in standard double-precision accuracy representing the number $1 + 10^{-16}$ **is not possible**. The computer therefore has to **round it to the next representable number**, which is itself $1$. Therefore """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$ba227f1d-542a-4d9b-adad-5e17755f3c30„§cell_idÙ$ba227f1d-542a-4d9b-adad-5e17755f3c30¤codeÙ•md""" ## Optional: Interpolating data Imagine now we did some measurement of the rate of a chemical reation at different temperatures, let's say """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$357aa8d2-9e50-48a2-8467-faf8c2ed90ad„§cell_idÙ$357aa8d2-9e50-48a2-8467-faf8c2ed90ad¤codeÚÜmd""" Moreover numerical approximations of derivatives are key ingredients when solving **differential equations**. For example, suppose we know that the voltage of an electrical system changes in time according to the derivative ```math \frac{d u(t)}{d t} = \sin\left[(u+t)^2\right] ``` and we know that at time $t=0$ the voltage is $u(0) = -1$. Our goal is to know the behaviour of $u(t)$ for *all future values* of $t$. As we will discuss towards the end of this course (in [Initial value problems](https://teaching.matmat.org/numerical-analysis/12_Initial_value_problems.html)), approximating the derivative $\frac{d u(t)}{d t}$ by a formula like (1) will lead to a family of numerical schemes, which achieves exactly that. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$848c7983-711a-44e5-939b-a705fd400ffa„§cell_idÙ$848c7983-711a-44e5-939b-a705fd400ffa¤codeÚ¦md""" #### Method 1 Using equations (2a) and (2b) we can derive the relationship ```math \tag{3} i = \frac{v_R}{R} = \frac{V - v_D}{R} ``` Rearranging (2c) in turn leads to ```math v_D = v_0 \log\left( \frac{i}{i_0} + 1\right). ``` Inserting (3) into this latter equation then gives ```math v_D = v_0 \log\left( \frac{V-v_D}{R\,i_0} + 1\right) ``` or by introducing the function ```math \tag{4} g_\text{log}(x) = v_0 \log\left( \frac{V - x}{R \, i_0} + 1 \right). ``` the problem ```math g_\text{log}(v_D) = v_D. ``` Problems of this form, where one seeks a point $v_D$ at which the function $g_\text{log}$ returns just the point itself are called **fixed-point problems**. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21„§cell_idÙ$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21¤codeÚ md"We observe that while indeed initially the error decreases as $h$ decreases at some point it starts to increase again with **results worse and worse**. With this slider you can check this is indeed the case for pretty much all values of $t$ where we take the derivative numerically: "¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7„§cell_idÙ$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7¤codeÚ md""" !!! info "Related questions we will discuss:" - There seems to be some **optimal value** for $h$. Is it independent of the function to be differentiated ? Can we **estimate the optimal value** somehow ? - With this algorithm there seems to be some minimal error we can achieve. Are there **more accurate derivative formulas** ? - The convergence plot as $h$ decreases seems to have the same slope (convergence rate) for all points $t$. Does this slope depend on $f$ ? How **can we reach faster convergence** ? """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897„§cell_idÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897¤codeÚemd""" We notice that the **representable numbers** get **less and less dense** as we move to to larger values --- a conclusion which remains true for double-precision floating-point numbers. This construction has one key advantage, namely that the **relative error due to rounding** remains finite. Or in other words if $fl(x)$ denotes the result of rounding the real number $x$ into the set of representable floating-point numbers, then !!! info "Definition: Machine epsilon" The **machine epsilon** $ε_M = β^{1-t}$ is the smallest real number greater than zero, such that $fl(1+ε_M) > 1$. The **roundoff error** $\frac{ε_M}{2}$ is an upper bound to the relative error in representing a real number $x \in \mathbb{R} \setminus \{0\}$, i.e. ```math \frac{|x - fl(x)|}{|x|} ≤ \frac{ε_M}{2} ``` Standard elementary floating-point operations (e.g. addition, subtraction, multiplication, division) have similarly at most a relative error of $\frac{ε_M}{2}$. E.g. for the case of adding two floating-point numbers $x$ and $y$ we have ```math \frac{|(x+y) - fl(x + y)|}{|x + y|} ≤ \frac{ε_M}{2}. ``` """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$cc19d720-ce62-469e-9323-12a79c4081e1„§cell_idÙ$cc19d720-ce62-469e-9323-12a79c4081e1¤codeÚ-let plot(h_values, errors; xaxis=:log, yaxis=:log, xflip=true, # Flip order of x axis ylims=(1e-8, 1), mark=:o, # Mark all points by circle xlabel="h", ylabel="Absolute error", linewidth=2, label="", xticks=10.0 .^ (-16:2:0), title="Error of derivative at t = $t0", ) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$06084cb6-0d9c-46eb-adb7-38b3b607d458„§cell_idÙ$06084cb6-0d9c-46eb-adb7-38b3b607d458¤codeÚ2begin # Pre-process data lines = split(data, "\n") temperature = [parse(Float64, split(line)[1]) for line in lines[2:end-1]] rate = [parse(Float64, split(line)[2]) for line in lines[2:end-1]] # Scatter plot scatter(temperature, rate, label="Observed rates", xlabel=L"T", ylabel=L"k", c=2) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$1dbb2e84-efb4-41b7-a31d-fc349c448a32„§cell_idÙ$1dbb2e84-efb4-41b7-a31d-fc349c448a32¤codeÚRmd""" How to get the most out of this course: - **All content** of the lecture is in the **online lecture notes**. Note that these are a **living document**. Expect them to improve over the semester based on errors we find or based on questions that come up during the lecture. - The **additional PDF documents** are provided as references. Their content is similar and they can serve you as additional learning resources. - The **blackboard derivations** is only **meant to slow me down** and give you the chance to follow the more technical parts of the derivations and ask questions about them. In principle **everything I say is also written down in the lecture notes**. It is up to you whether you **just want to listen**, you **want to copy all discussion** on the blackboard or you simply **print or otherwise annotate the PDFs** we provide online. - The **expectation is *not* that you leave the lecture understanding everything** that is said, much rather that you will understand it after you go through the lecture notes once again for yourself. - With that said **it can be helpful to read through the lecture notes** for the next session **before going to the session** itself. - In the lecture **I often pause and ask for questions**. This is your chance to slow me down in case you are lost: **any question is appreciated**. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2„§cell_idÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2¤codeÙ)md"""and apply this function 10 times:"""¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$d0257ff3-6873-44df-886d-0236f0b729ea„§cell_idÙ$d0257ff3-6873-44df-886d-0236f0b729ea¤codeÚAmd""" Clearly between $0$ and $1$ the function changes quite rapidly. To investigate the **acceleration** there **we take the derivative**. This can be done by hand, but instead we will employ a Julia package (namely [`Symbolics`](https://symbolics.juliasymbolics.org/)) to take the derivative for us. The result is: """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$c9aac823-6556-4a98-92e4-7e8631e7b71e„§cell_idÙ$c9aac823-6556-4a98-92e4-7e8631e7b71e¤codeÙØ# Block installing Julia packages needed to run this notebook. begin using Plots using PlutoUI using PlutoTeachingTools using LaTeXStrings using Symbolics using NLsolve using HypertextLiteral using Printf end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$c07c1593-bfa1-44ea-8320-aa20b259a0cf„§cell_idÙ$c07c1593-bfa1-44ea-8320-aa20b259a0cf¤codeÙ¹md""" !!! info "Related questions we will discuss:" - What measures can we take to keep floating-point error small in algorithms, such as the numerical computation of derivatives ? """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$459361fa-2abd-49ec-aa88-8e37e679c782„§cell_idÙ$459361fa-2abd-49ec-aa88-8e37e679c782¤codeÚkmd""" After 10 steps about 12 significant figures have stabilised, so we seem to obtain convergence to a value $v_D$, i.e. mathematically ```math \lim_{k\to\infty} v^{(k)}_D = v_D. ``` At this point we have $v_D = g_\text{log}(v_D)$ (otherwise the iteration would not stabilise). Since ```math v_D = g_\text{log}(v_D) = v_0 \log\left( \frac{V - v_D}{R \, i_0} + 1 \right) ``` one can show that this voltag $v_D$ actually satisfies equations (2a) to (2c) simultaneously, i.e. satisfies the diode equation. Just by repeatedly applying $g_\text{log}$ we obtained **a numerical algorithm to solve the diode problem**. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$a089a707-ff05-4bdb-bd31-1422617388fc„§cell_idÙ$a089a707-ff05-4bdb-bd31-1422617388fc¤codeÚmd""" # Introduction ## Opening remarks [Slides of the presentation on Moodle](https://teaching.matmat.org/): These summarise the following paragraphs and the content of the course in a short presentation. In modern practice **every scientist employs computers**. Some use them to symbolically derive equations for complex theories, others perform simulations, yet others analyse and visualise experimental results. In all these cases we encounter **mathematical problems**, which we need to **solve using numerical techniques**. The point of this lecture is to learn how to **formalise such numerical procedures** mathematically, **implement them** using the [Julia programming language](https://julialang.org/) and **analyse using pen and paper** why some methods work better, some worse and some not at all. You might think learning about this is a bit of an overkill and probably not very useful for your future studies. But let us look at a few examples, which give an overview what we will study in more depth throughout the course. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$a6c77495-b336-40b2-afaf-184d96b4dce9„§cell_idÙ$a6c77495-b336-40b2-afaf-184d96b4dce9¤codeÙlet vD = 0.1 for i in 1:10 vD = gexp(vD) # Call fixed-point map @printf "iter %2i: vD = %.15f\n" i vD # Print formatted data end end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$079e9f17-27a2-4284-b283-09e6aadbc53b„§cell_idÙ$079e9f17-27a2-4284-b283-09e6aadbc53b¤codeÚumd""" ### Structure of floating-point numbers As we found out above in practice the **set of floating-point numbers** is much smaller than the set of real numbers $\mathbb{R}$ and **not all numbers can be represented as a floating-point numbers**. This leads to the natural question: **which numbers can be represented** on a computer. Answering this in all details is beyond the scope of this course (see for example for more information). However, getting some intuition is helpful to obtain a feeling how large floating-point errors can be. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcf„§cell_idÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcf¤codeÚAmd""" !!! info "Related questions we will discuss:" - How can I understand whether an obtained numerical answer is credible ? - What techniques based on visualisation or plotting help me to understand the accuracy of a numerical algorithm ? - How can I understand under which conditions algorithms converge ? - If they do not converge, how can I overcome numerical issues ? - What are numerically stable techniques for solving standard scientific problems ? - How can I understand and evaluate the speed of convergence of an algorithm and improve it even further ? """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$2255ea65-76a7-403b-af0a-d9dd489b105c„§cell_idÙ$2255ea65-76a7-403b-af0a-d9dd489b105c¤codeÚÌmd""" Clearly far from a handy expression and not the kind of derivative one wants to compute by hand. So let us **compute this derivative numerically** instead. An idea to do so goes back to the definition of the derivative $v'(t)$ as the limit $h\to 0$ of the slope of secants over an intervall $[t, t+h]$, i.e. ```math v'(t) = \lim_{h\to 0} \frac{v(t+h) - v(t)}{h}. ``` A natural idea is to not fully take the limit, i.e. to take a small $h > 0$ and approximate ```math \tag{1} v'(t) ≈ \frac{v(t+h) - v(t)}{h}. ``` The expectation is that as we take smaller and **smaller values for $h$**, this **converges to the exact derivatives**. So let's try this at the point `t0 = ` $t0 for various values for `h` """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80d„§cell_idÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80d¤codeÚÄmd""" ## Representing numbers on a computer Let us try to shed some light why results in the previous example on numerically computing derivatives get worse and worse as we take smaller stepsizes $h$. For this purpose let us reconsider the expression for approximating the derivative $v'(t)$, which we obtained in (1), namely ```math v'(t) ≈ \frac{v(t+h) - v(t)}{h}. ``` As we saw when $h$ gets smaller this approximation gets worse in practice. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$b192ec68-836c-4fb0-8f03-6ebb01cfcf68„§cell_idÙ$b192ec68-836c-4fb0-8f03-6ebb01cfcf68¤codeÚ6md""" ## Taking derivatives Before we dive into the main content of the course, the remainder of this chapter provides some examples for numerical problems and their challenges when solving them numerically. These examples serve to pose motivating questions, which we seek to answer throughout the course. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$71c91579-a894-44b5-b4d7-f8d98667b977„§cell_idÙ$71c91579-a894-44b5-b4d7-f8d98667b977¤code±TableOfContents()¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$5a609e3e-ed94-4e4e-b9e4-c70fd459a25c„§cell_idÙ$5a609e3e-ed94-4e4e-b9e4-c70fd459a25c¤codeÚ©md""" We first consider the problem of **taking derivatives**. Derivatives characterise the change of a quantity of interest. E.g. the acceleration as a derivative of the velocity indeed characterises how the velocity changes over time. More broadly any experiment in physics or engineering operates by imposing a change to a material or chemical system (e.g. changing temperature, pressure, stress etc.) and observing how it reacts. As a result **derivatives are therefore at the heart of physics and engineering** and appear everywhere in these subjects. But computing derivatives by hand is not always easy. To see this consider the **innocent-looking velocity function**. """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3„§cell_idÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3¤codeÙ1begin t = 1 h = 1e-16 ( (t + h) - t ) / h end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$ae449fa8-76c9-4d1d-af05-464692436727„§cell_idÙ$ae449fa8-76c9-4d1d-af05-464692436727¤codeÚpmd""" Clearly, the quality of such a fit depends strongly on the polynomial order. Perhaps suprising is, however, that **higher degree is not necessarily better**. We will discuss why this is. !!! info "Related questions we will discuss:" - How can I fit a parametric model (e.g. the above polynomial) to data points ? - How accurate can I expect such a polynomial fit to be ? - Can I choose an optimal polynomial order to obtain the most accurate answer ? - If I have control over the strategy to acquire data (e.g. how to design my lab experiment), can I have an influence on the accuracy of such interpolations ? """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$3710d552-729f-4e41-9da2-1756907c4ced„§cell_idÙ$3710d552-729f-4e41-9da2-1756907c4ced¤codeÙ3function gexp(vD) V - R * i0 * (exp(vD/v0)-1) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$7d265705-3ef0-4974-bfcc-ee25707dee1e„§cell_idÙ$7d265705-3ef0-4974-bfcc-ee25707dee1e¤code®1 + 1e-16 == 1¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$eacbce03-d987-4d20-bc56-815c4f5f4907„§cell_idÙ$eacbce03-d987-4d20-bc56-815c4f5f4907¤codeÙ³begin using ForwardDiff # Package for computing derivatives of Julia functions reference = ForwardDiff.derivative(v, t0) errors = [abs(d - reference) for d in derivatives] end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$ac1a0435-6447-45fc-97b6-475e8586eebd„§cell_idÙ$ac1a0435-6447-45fc-97b6-475e8586eebd¤codeÚ@let RobustLocalResource("https://teaching.matmat.org/numerical-analysis/sidebar.md", "sidebar.md") Sidebar(toc, ypos) = @htl("""""") # Sidebar(Markdown.parse(read("sidebar.md", String)), 300) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31a„§cell_idÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31a¤codeÚömd""" As we will see in the next lectures there are a number of numerical techniques to solve such nonlinear fixed-point problems $g(x) = x$. Each of these have their advantages and disadvantages and hardly any of them just work. Let us also note already here that **fixed-point problems are closely related to root-finding problems** (*frz. trouver des zéros*). Namely if $x$ is a fixed-point of $g$ than it is a root of $f(x) = g(x) - x$. Often for a scientific problem there are **many choices how to formulate it as a fixed-point or root-finding problem**. Therefore there are usually **many choices how to solve the same problem on a computer**. As we saw above not all of these options work equally well. This immediately raises some questions: """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6„§cell_idÙ$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6¤codeÙLmd" `t0 = ` $(@bind t0 Slider(-1.0:0.1:1.0; show_value=true, default=0.2)) "¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedënotebook_idÙ$fb576a92-3820-11f1-9f89-cf97c88e7704¥bonds€¬cell_resultsÞEÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2Š¦queued¤logs§running¦output†¤bodyÚT

The set of floating-point numbers has elements of the form

$$y = \pm m \, \beta^{e-t}.$$

It is thus characterised by four integer parameters:

In the definition of $y$ the integer $m$ is the significand (or mantissa), which has $t$ number of digits, i.e. $m = (a_1 a_2 \cdots a_t)$, which satisfy $0 < a_1 \leq β-1$ and $0 ≤ a_i ≤ β-1$ for $i=2,\ldots,t$.

The most common case are double-precision floating-point numbers with $β=2$, $t = 24$, $e_\text{min} = -1023$ and $e_\text{max} = +1022$.

This is unfortunately too many numbers to illustrate easily. To still get a visual representation of the "denseness" of floating-point numbers, we therefore consider a toy case with $\beta = 2$, $t = 3$, $e_\text{min} = -1$ and $e_\text{max} = 3$. Considering only the positive numbers, the following numbers can be represented:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£VÄ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$1b1e6f9b-a6db-4dd4-bcbf-f7a0cb24cca2¹depends_on_disabled_cells§runtimeδLµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2Š¦queued¤logs§running¦output†¤bodyÙM

which explains the zero result we obtain.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£VOY·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$1a301715-4734-4ae0-91c0-51e2cb0eadb2¹depends_on_disabled_cells§runtimeεpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3Š¦queued¤logs§running¦output†¤bodyÚl

How this course works

Context of the course:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£T x·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$8c94a651-312d-4b28-93ef-5152d2ebd4d3¹depends_on_disabled_cells§runtimeÎ iµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$990863df-8549-434a-acb0-22207a4df287Š¦queued¤logs§running¦output†¤bodyÈßC °persist_js_state¤mime­image/svg+xml²last_run_timestampËAÚw›ï˜F|·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$990863df-8549-434a-acb0-22207a4df287¹depends_on_disabled_cells§runtimeÎut:ìµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$ed573aed-09e2-47ff-8b91-fdd14f3bee0fŠ¦queued¤logs§running¦output†¤bodyÚé

which consists of

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£X-Ï·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$ed573aed-09e2-47ff-8b91-fdd14f3bee0f¹depends_on_disabled_cells§runtimeÎ àüµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$86590ede-19cd-4610-baa4-eb3f1286bd67Š¦queued¤logs§running¦output†¤bodyÚ

Even if you now might think, that your heart beats for experimental research and you will never need numerics, keep in mind that all data analysis uses procedures based on such techniques. Even commercial packages for experimental post-processing rely heavily on the procedures we will cover and sometimes get it wrong. See for example this report on Microsoft Excel). This can and has compromised scientific fundings in the past. Therefore it's best to be prepared, so you can judge what is wrong: The experiment or the numerics.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£YÜ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$86590ede-19cd-4610-baa4-eb3f1286bd67¹depends_on_disabled_cells§runtimeÎdʵpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542bŠ¦queued¤logs§running¦output†¤body °persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›î—3·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$7047b5e6-24df-4d22-b4ca-e2872ecb542b¹depends_on_disabled_cells§runtimeÍgèµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfcŠ¦queued¤logs§running¦output†¤bodyÙã

namely because $10^{-16}$ is smaller than the machine epsilon, such that $fl(1 + 10^{-16}) = 1$.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£WV*·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$c1c530b0-076e-4fc0-a0dd-ce2a2bc9cbfc¹depends_on_disabled_cells§runtimeÎmAµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$f01345c5-3b96-40f1-8ed3-0fbe85f908d9Š¦queued¤logs§running¦output†¤bodyÚ J

Still, it seems reasonable that we should be able to determine some continuous function $f$ from the observed data, which establishes a good model for the relationship $k = f(T)$. Albeit $255 K$ has not been measured, we can thus evaluate $f(255 K)$ and get an estimate for the rate at this temperature. Since the new temperature $255 K$ islocated within the observed data range (i.e. here $250K$ to $350K$) we call this procedure interpolation.

In this lecture we will discuss some common interpolation techniques. In particular we will develop the mathematical formalism for these techniques and –- most importantly –- we will use this formalism to understand conditions when these methods work and when these methods fail.

In fact our example here is already a little tricky. Let us illustrate this point for polynomial interpolation, one particularly frequent technique. Without going into details for now, one basic idea is to fit a polynomial of degree $N$

$$k(T) = \sum_{n=1}^{N} α_n T^n$$

to the data. By some procedure discussed later we thus determine the unknown polynomial coefficients $α_n$, such that the polynomial best matches our observations and use that to determine $f(255 K)$.

Let's see the result of such a fit. The slider let's you play with the polynomial order:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›îúÙ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$f01345c5-3b96-40f1-8ed3-0fbe85f908d9¹depends_on_disabled_cells§runtimeÎÙdJµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474fŠ¦queued¤logs§running¦output†¤bodyÚÈ

$$\begin{equation} 64 ~ \left( 1 - 8 ~ t + 8 ~ t^{2} \right)^{2} ~ \left( 1 - 2 ~ t \right)^{2} ~ \left( 1 - t \right) - 64 ~ \left( 1 - 8 ~ t + 8 ~ t^{2} \right)^{2} ~ \left( 1 - 2 ~ t \right)^{2} ~ t - 256 ~ \left( 1 - 8 ~ t + 8 ~ t^{2} \right)^{2} ~ \left( 1 - 2 ~ t \right) ~ t ~ \left( 1 - t \right) + 128 ~ \left( 1 - 2 ~ t \right)^{2} ~ t ~ \left( 1 - t \right) ~ \left( -8 + 16 ~ t \right) ~ \left( 1 - 8 ~ t + 8 ~ t^{2} \right) \end{equation}$$

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›î &зhas_pluto_hook_features¬rootassigneeÀ§cell_idÙ$2dad6ffd-92a2-4b60-9e33-ea978dba474f¹depends_on_disabled_cells§runtimeϾęüµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$4e2edbda-28ae-4978-a94a-1d23766d4937Š¦queued¤logs§running¦output†¤bodyÙB

We can plot it to get an idea:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£TÍ…·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$4e2edbda-28ae-4978-a94a-1d23766d4937¹depends_on_disabled_cells§runtimeÎ)µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$d55c983f-16bb-484a-9c2f-80b8e3b010b8Š¦queued¤logs§running¦output†¤bodyÙ`

For double-precision numbers we have for the machine epsilon

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£WÆ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$d55c983f-16bb-484a-9c2f-80b8e3b010b8¹depends_on_disabled_cells§runtimeÎ2iµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c736d68f-95f1-47c6-bd75-13d62a895e12Š¦queued¤logs§running¦output†¤bodyµ2.220446049250313e-16°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›îg'š·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$c736d68f-95f1-47c6-bd75-13d62a895e12¹depends_on_disabled_cells§runtimeÍ_kµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aaŠ¦queued¤logs§running¦output†¤bodyÚg

Takeaway: Properties of double-precision numbers

For standard double-precision floating-point numbers (Float64) we have $ε_M ≈ 2 \cdot 10^{-16}$, such that floating-point operations are accurate to a relative error of $\frac{ε_M}{2} ≈ 10^{-16}$.

Tip: This is the only information you need to remember about the structure of floating-point numbers for this class.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£W‚ ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$3e4cf748-d198-4745-9d8b-5d3bd8c618aa¹depends_on_disabled_cells§runtimeÎ@͵published_object_keys¸depends_on_skipped_cells§erroredÂÙ$349d6db7-2b93-4833-ac0a-c0c398133814Š¦queued¤logs§running¦output†¤body¤true°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›îgÜ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$349d6db7-2b93-4833-ac0a-c0c398133814¹depends_on_disabled_cells§runtimeÍ2Iµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076Š¦queued¤logs§running¦output†¤body…¨elementsÜ!’’§1.0e-15ªtext/plain’’«3.16228e-15ªtext/plain’’§1.0e-14ªtext/plain’’«3.16228e-14ªtext/plain’’§1.0e-13ªtext/plain’’«3.16228e-13ªtext/plain’’§1.0e-12ªtext/plain’’«3.16228e-12ªtext/plain’ ’§1.0e-11ªtext/plain’ ’«3.16228e-11ªtext/plain’ ’§1.0e-10ªtext/plain’ ’«3.16228e-10ªtext/plain’ ’¦1.0e-9ªtext/plain’’ª3.16228e-9ªtext/plain’’¦1.0e-8ªtext/plain’’ª3.16228e-8ªtext/plain’’¦1.0e-7ªtext/plain’’ª3.16228e-7ªtext/plain’’¦1.0e-6ªtext/plain’’ª3.16228e-6ªtext/plain’’¦1.0e-5ªtext/plain’’ª3.16228e-5ªtext/plain’’¦0.0001ªtext/plain’’«0.000316228ªtext/plain’’¥0.001ªtext/plain’’ª0.00316228ªtext/plain’’¤0.01ªtext/plain’’©0.0316228ªtext/plain’’£0.1ªtext/plain’’¨0.316228ªtext/plain’’£1.0ªtext/plain’ ’§3.16228ªtext/plain’!’¤10.0ªtext/plain¬prefix_short ¨objectid°10c3e4e55f76d0b7¦prefix§Float64¤type¥Array°persist_js_state¤mimeÙ!application/vnd.pluto.tree+object²last_run_timestampËAÚw›è7C-·has_pluto_hook_features¬rootassignee¨h_values§cell_idÙ$25b75acf-9cf7-4aa7-a7ec-7d80ee68d076¹depends_on_disabled_cells§runtimeÎaSíµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$e21c528a-bc5e-448a-922f-97fc029a37ebŠ¦queued¤logs§running¦output†¤bodyÙ;

which finally explains

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£W5L·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$e21c528a-bc5e-448a-922f-97fc029a37eb¹depends_on_disabled_cells§runtimeεpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$06a18358-597b-4532-a735-5031a544c034Š¦queued¤logs§running¦output†¤bodyÚ

Now we are curious about the rates at another temperature, say $255 K$. The basic laws of thermodynamics and chemical kinetics tell us that the rate should be a continuous function of the temperature. For example Arrhenius' law

$$\tag{4} k(T) = A \exp\left( - \frac{E_A}{k_B T} \right)$$

establishes such a relationship, where $A$, $E_A$ and $k_B$ are some constants. Note, that in this case the behaviour is more complicated as is immediately obvious from a plot of the observed data:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Yàe·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$06a18358-597b-4532-a735-5031a544c034¹depends_on_disabled_cells§runtimeÎÙ°µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$dbe26026-6f55-4664-a4f6-77f30eb225deŠ¦queued¤logs§running¦output†¤body…¨elementsÜ!’’§8.99281ªtext/plain’’¦9.0755ªtext/plain’’§9.05942ªtext/plain’’§9.06497ªtext/plain’’§9.06719ªtext/plain’’§9.06567ªtext/plain’’§9.06603ªtext/plain’’§9.06608ªtext/plain’ ’§9.06609ªtext/plain’ ’§9.06609ªtext/plain’ ’§9.06609ªtext/plain’ ’§9.06609ªtext/plain’ ’§9.06609ªtext/plain’’§9.06609ªtext/plain’’§9.06609ªtext/plain’’§9.06609ªtext/plain’’§9.06609ªtext/plain’’¦9.0661ªtext/plain’’§9.06612ªtext/plain’’§9.06619ªtext/plain’’§9.06642ªtext/plain’’§9.06715ªtext/plain’’§9.06945ªtext/plain’’§9.07668ªtext/plain’’§9.09913ªtext/plain’’§9.16608ªtext/plain’’§9.33784ªtext/plain’’§9.49806ªtext/plain’’§7.05331ªtext/plain’’©-0.860926ªtext/plain’’¨-256.981ªtext/plain’ ’ª-2.19432e7ªtext/plain’!’«-1.27727e11ªtext/plain¬prefix_short ¨objectid°e97209398ed0201c¦prefix§Float64¤type¥Array°persist_js_state¤mimeÙ!application/vnd.pluto.tree+object²last_run_timestampËAÚw›èÃê>·has_pluto_hook_features¬rootassignee«derivatives§cell_idÙ$dbe26026-6f55-4664-a4f6-77f30eb225de¹depends_on_disabled_cells§runtimeÍnqµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$06867a4c-c4b0-47a5-9678-22baab9ca83fŠ¦queued¤logs§running¦output†¤bodyÚ

Even though the method 2 seems equally plausible as method 1 on first sight, method 2 does not converge. As a result this method is not helpful to us to obtain the fixed point / the diode voltage.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£YI·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$06867a4c-c4b0-47a5-9678-22baab9ca83f¹depends_on_disabled_cells§runtimeÎx µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaafŠ¦queued¤logs‘ˆ¤lineÿ£msg’ÚJiter 1: vD = 0.064185388617239 iter 2: vD = 0.066052822568595 iter 3: vD = 0.065956308405801 iter 4: vD = 0.065961298808626 iter 5: vD = 0.065961040778816 iter 6: vD = 0.065961054120317 iter 7: vD = 0.065961053430491 iter 8: vD = 0.065961053466159 iter 9: vD = 0.065961053464315 iter 10: vD = 0.065961053464410 ªtext/plain§cell_idÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaaf¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§running¦output†¤body °persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›îÁ+õ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$9a8dae54-d4ea-47bf-8f77-54286cedcaaf¹depends_on_disabled_cells§runtimeÎ ¶˜µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$f4a47680-4ab6-4d51-80da-1cdecc53cde2Š¦queued¤logs§running¦output†¤bodyÚ2Õ°persist_js_state¤mime©text/html²last_run_timestampËAÚw›î”2ø·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$f4a47680-4ab6-4d51-80da-1cdecc53cde2¹depends_on_disabled_cells§runtimeÎ@ì×µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$e57539a7-d8fb-413d-be9e-d2459ed65610Š¦queued¤logs§running¦output†¤bodyÚ>

Note that, since $f$ is not just a simple polynomial, but a non-linear function there is no explicit analytic formula for finding its solution. We therefore need to consider iterative approaches.

Interestingly enough in this case simple repeated iteration, i.e.

$$v^{(k+1)}_D = g_\text{log}(v^{(k)}_D) \qquad \text{for $k = 1, 2, \ldots$},$$

just works to find the fixed point. To see that we select the parameters

and define the fixed-point map

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›î›Zæ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$e57539a7-d8fb-413d-be9e-d2459ed65610¹depends_on_disabled_cells§runtimeÎzöµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0Š¦queued¤logs§running¦output†¤bodyÙX

... and compute the error against a reference value:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£U5 ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$c38dd3f6-5d08-4398-bdac-2765cf77e8a0¹depends_on_disabled_cells§runtimeÎOµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66Š¦queued¤logs§running¦output†¤bodyÚª

Errors in algorithms can be much larger than machine epsilon

ust because the relative error of an individual floating-point operation is bounded by $\frac{ε_M}{2}$, this does not imply that the error of an algorithm is bounded by this value. This is exactly what we saw in the numerical differentiation example above, where the observed error in the computed derivative amounts to values well beyond $\frac{ε_M}{2}$, such that all accuracy in the final answer is lost.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£W¤ð·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$bf46aaed-3343-4b05-98e8-c6abd2800c66¹depends_on_disabled_cells§runtimeÎc§µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209Š¦queued¤logs§running¦output†¤bodyÚS

Fixed-point problems

The previous discussion was mostly centred around the accuracy of a computation. In this example we will get some first idea about the challenges when designing a good numerical algorithm.

We consider the simple Diode model circuit

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Wí¢·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$4f9ed1a2-bb88-11ee-07bf-eb30cea74209¹depends_on_disabled_cells§runtimeÎe8µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$dbbedfb0-f011-431c-8302-9e46a8ad32ffŠ¦queued¤logs§running¦output†¤bodyÈÂ8 °persist_js_state¤mime­image/svg+xml²last_run_timestampËAÚw›îf;·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$dbbedfb0-f011-431c-8302-9e46a8ad32ff¹depends_on_disabled_cells§runtimeÎ PÍ`µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$41eb08d1-14c8-4d04-9216-aec0304581beŠ¦queued¤logs§running¦output†¤bodyÚ

Let us disect one particular example in detail. We consider $v(t) = t$, where one computes

$$\frac{v(t+h) - v(t)}{h} = \frac{(t+h)-t}{h},$$

which is clearly equal to $1$ independent of the choice of $h$. However, computing this expression numerically for $h=10^{-16}$ we observe

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£V ö·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$41eb08d1-14c8-4d04-9216-aec0304581be¹depends_on_disabled_cells§runtimeÎ[µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9fŠ¦queued¤logs§running¦output†¤bodyÚè

We now want to solve this problem numerically, that is find the Diode voltage $v_D$ and the current $i$ from the parameters $R$, $V$, $i_0$ and $v_0$.

If you have never encountered circuit theory, just take it for granted that we now have a problem consisting of the three equations

$$\begin{align} \tag{2a} V &= v_D + v_R \\ \tag{2b} v_R &= R\, i \\ \tag{2c} i &= i_0 (e^{v_D / v_0} - 1) \end{align}$$

where $v_D$ is the unknown we want to determine.

Our goal is to model this circuit, i.e. understand the current $i$ and its voltage $v_D$ across the circuit elements.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£XXK·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$fafdfb0d-9a0f-42a4-84db-465a24361d9f¹depends_on_disabled_cells§runtimeÎÁµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$51ba2f16-d610-401c-a1d8-6af94dbbdd09Š¦queued¤logs§running¦output†¤bodyÙQ

Finally we plot the errors on a log-log plot:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£UP ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$51ba2f16-d610-401c-a1d8-6af94dbbdd09¹depends_on_disabled_cells§runtimeÎü]µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$7b74843b-1198-40fb-a89f-9dd86738c2cdŠ¦queued¤logs§running¦output†¤body °persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›îÍ-„·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$7b74843b-1198-40fb-a89f-9dd86738c2cd¹depends_on_disabled_cells§runtimeÍ0öµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$cfc885de-9dd9-4008-9124-fbd31a799535Š¦queued¤logs§running¦output†¤bodyÈfc °persist_js_state¤mime­image/svg+xml²last_run_timestampËAÚw›è BJ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$cfc885de-9dd9-4008-9124-fbd31a799535¹depends_on_disabled_cells§runtimeÎœc¯Kµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$f8bf0e47-0089-4553-8604-cd8347345658Š¦queued¤logs§running¦output†¤bodyÙ"v (generic function with 1 method)°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›åðñJ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$f8bf0e47-0089-4553-8604-cd8347345658¹depends_on_disabled_cells§runtimeÎ ýµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$2604b66d-2c44-44b9-837c-9894f104adfcŠ¦queued¤logs§running¦output†¤bodyÙ%glog (generic function with 1 method)°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›î£ ‰·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$2604b66d-2c44-44b9-837c-9894f104adfc¹depends_on_disabled_cells§runtimeÎÀ˵published_object_keys¸depends_on_skipped_cells§erroredÂÙ$67e61788-2000-4fe4-8a14-48faa2df5bbdŠ¦queued¤logs§running¦output†¤bodyÙÜ

Click here to view the PDF version.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£S–³·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$67e61788-2000-4fe4-8a14-48faa2df5bbd¹depends_on_disabled_cells§runtimeΔZµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$76721956-b2e1-4b33-b5f3-fca94b4a89b2Š¦queued¤logs§running¦output†¤bodyÚŸ

Method 2

Now the arguments to introduce Method 1 were in fact a little convoluted. Let's try to directly balance the voltage across the circuit, i.e. directly employ $V = v_R + v_D$. Then using equations (2a) to (2c) this leads to:

$$\tag{5} V = v_R + v_D = R\, i + v_D = R \, i_0 \left( e^{v_D/v_0} - 1 \right) + v_D$$

or

$$V - R \, i_0 \left( e^{v_D/v_0} - 1 \right) = v_D$$

Introducing a function

$$\tag{6} g_\text{exp}(x) = V - R \, i_0 \left( e^{x/v_0} - 1 \right).$$

we again observe a fixed-point problem $g_\text{exp}(v_D) = v_D$. We again iterate as before:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Xì-·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$76721956-b2e1-4b33-b5f3-fca94b4a89b2¹depends_on_disabled_cells§runtimeÎc­µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$be44b23a-fd7f-4536-96c0-cd1c7326294dŠ¦queued¤logs§running¦output†¤bodyÙq

We compute the derivatives at each value for $h$ ...

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£UÇ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$be44b23a-fd7f-4536-96c0-cd1c7326294d¹depends_on_disabled_cells§runtimeÎ*ѵpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$75610334-8c66-4ef8-b108-68cdaa189721Š¦queued¤logs§running¦output†¤bodyÚï

which is clearly wrong.

We are faced with this error because the representation of numbers on a computer has only finite precision. In fact in standard double-precision accuracy representing the number $1 + 10^{-16}$ is not possible. The computer therefore has to round it to the next representable number, which is itself $1$. Therefore

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£V4j·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$75610334-8c66-4ef8-b108-68cdaa189721¹depends_on_disabled_cells§runtimeÎ_µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$ba227f1d-542a-4d9b-adad-5e17755f3c30Š¦queued¤logs§running¦output†¤bodyÙÚ

Optional: Interpolating data

Imagine now we did some measurement of the rate of a chemical reation at different temperatures, let's say

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Y»ª·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$ba227f1d-542a-4d9b-adad-5e17755f3c30¹depends_on_disabled_cells§runtimeÎÁöµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$357aa8d2-9e50-48a2-8467-faf8c2ed90adŠ¦queued¤logs§running¦output†¤bodyÚ"

Moreover numerical approximations of derivatives are key ingredients when solving differential equations. For example, suppose we know that the voltage of an electrical system changes in time according to the derivative

$$\frac{d u(t)}{d t} = \sin\left[(u+t)^2\right]$$

and we know that at time $t=0$ the voltage is $u(0) = -1$. Our goal is to know the behaviour of $u(t)$ for all future values of $t$.

As we will discuss towards the end of this course (in Initial value problems), approximating the derivative $\frac{d u(t)}{d t}$ by a formula like (1) will lead to a family of numerical schemes, which achieves exactly that.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£UÍ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$357aa8d2-9e50-48a2-8467-faf8c2ed90ad¹depends_on_disabled_cells§runtimeνsµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$848c7983-711a-44e5-939b-a705fd400ffaŠ¦queued¤logs§running¦output†¤bodyÚl

Method 1

Using equations (2a) and (2b) we can derive the relationship

$$\tag{3} i = \frac{v_R}{R} = \frac{V - v_D}{R}$$

Rearranging (2c) in turn leads to

$$v_D = v_0 \log\left( \frac{i}{i_0} + 1\right).$$

Inserting (3) into this latter equation then gives

$$v_D = v_0 \log\left( \frac{V-v_D}{R\,i_0} + 1\right)$$

or by introducing the function

$$\tag{4} g_\text{log}(x) = v_0 \log\left( \frac{V - x}{R \, i_0} + 1 \right).$$

the problem

$$g_\text{log}(v_D) = v_D.$$

Problems of this form, where one seeks a point $v_D$ at which the function $g_\text{log}$ returns just the point itself are called fixed-point problems.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£X…¥·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$848c7983-711a-44e5-939b-a705fd400ffa¹depends_on_disabled_cells§runtimeÎîµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21Š¦queued¤logs§running¦output†¤bodyÚ„

We observe that while indeed initially the error decreases as $h$ decreases at some point it starts to increase again with results worse and worse.

With this slider you can check this is indeed the case for pretty much all values of $t$ where we take the derivative numerically:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Up‚·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$2a14ebb1-e9a9-4dd6-87e1-afc7e8bc0d21¹depends_on_disabled_cells§runtimeγOµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7Š¦queued¤logs§running¦output†¤bodyÚ*

Related questions we will discuss:

  • There seems to be some optimal value for $h$. Is it independent of the function to be differentiated ? Can we estimate the optimal value somehow ?

  • With this algorithm there seems to be some minimal error we can achieve. Are there more accurate derivative formulas ?

  • The convergence plot as $h$ decreases seems to have the same slope (convergence rate) for all points $t$. Does this slope depend on $f$ ? How can we reach faster convergence ?

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£U£ì·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$9aed0528-8e7e-477b-bc1f-0fd3e76bddd7¹depends_on_disabled_cells§runtimeÎ ôšµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897Š¦queued¤logs§running¦output†¤bodyÚÓ

We notice that the representable numbers get less and less dense as we move to to larger values –- a conclusion which remains true for double-precision floating-point numbers.

This construction has one key advantage, namely that the relative error due to rounding remains finite. Or in other words if $fl(x)$ denotes the result of rounding the real number $x$ into the set of representable floating-point numbers, then

Definition: Machine epsilon

The machine epsilon $ε_M = β^{1-t}$ is the smallest real number greater than zero, such that $fl(1+ε_M) > 1$. The roundoff error $\frac{ε_M}{2}$ is an upper bound to the relative error in representing a real number $x \in \mathbb{R} \setminus \{0\}$, i.e.

$$\frac{|x - fl(x)|}{|x|} ≤ \frac{ε_M}{2} $$

Standard elementary floating-point operations (e.g. addition, subtraction, multiplication, division) have similarly at most a relative error of $\frac{ε_M}{2}$. E.g. for the case of adding two floating-point numbers $x$ and $y$ we have

$$\frac{|(x+y) - fl(x + y)|}{|x + y|} ≤ \frac{ε_M}{2}.$$

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Vûj·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$3ac6950d-be6c-41c8-8d31-3bdb437c5897¹depends_on_disabled_cells§runtimeΠ˵published_object_keys¸depends_on_skipped_cells§erroredÂÙ$cc19d720-ce62-469e-9323-12a79c4081e1Š¦queued¤logs§running¦output†¤bodyÈæÔ °persist_js_state¤mime­image/svg+xml²last_run_timestampËAÚw›éYê·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$cc19d720-ce62-469e-9323-12a79c4081e1¹depends_on_disabled_cells§runtimeÎíVþµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$06084cb6-0d9c-46eb-adb7-38b3b607d458Š¦queued¤logs§running¦output†¤bodyÈ“ °persist_js_state¤mime­image/svg+xml²last_run_timestampËAÚw›îíyÙ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$06084cb6-0d9c-46eb-adb7-38b3b607d458¹depends_on_disabled_cells§runtimeÎyîµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$1dbb2e84-efb4-41b7-a31d-fc349c448a32Š¦queued¤logs§running¦output†¤bodyÚˆ

How to get the most out of this course:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£TeÜ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$1dbb2e84-efb4-41b7-a31d-fc349c448a32¹depends_on_disabled_cells§runtimeÎ1µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2Š¦queued¤logs§running¦output†¤bodyÙE

and apply this function 10 times:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£X ”·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$6ca86375-b191-4b15-8162-e65cad4d3aa2¹depends_on_disabled_cells§runtimeÎ µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$d0257ff3-6873-44df-886d-0236f0b729eaŠ¦queued¤logs§running¦output†¤bodyÚË

Clearly between $0$ and $1$ the function changes quite rapidly. To investigate the acceleration there we take the derivative.

This can be done by hand, but instead we will employ a Julia package (namely Symbolics) to take the derivative for us. The result is:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Tôº·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$d0257ff3-6873-44df-886d-0236f0b729ea¹depends_on_disabled_cells§runtimeδCµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c9aac823-6556-4a98-92e4-7e8631e7b71eŠ¦queued¤logs§running¦output†¤body °persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›ä\´ ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$c9aac823-6556-4a98-92e4-7e8631e7b71e¹depends_on_disabled_cells§runtimeÎÉk5lµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c07c1593-bfa1-44ea-8320-aa20b259a0cfŠ¦queued¤logs§running¦output†¤bodyÚ

Related questions we will discuss:

  • What measures can we take to keep floating-point error small in algorithms, such as the numerical computation of derivatives ?

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£WÉæ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$c07c1593-bfa1-44ea-8320-aa20b259a0cf¹depends_on_disabled_cells§runtimeÎ(£µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$459361fa-2abd-49ec-aa88-8e37e679c782Š¦queued¤logs§running¦output†¤bodyÚ±

After 10 steps about 12 significant figures have stabilised, so we seem to obtain convergence to a value $v_D$, i.e. mathematically

$$\lim_{k\to\infty} v^{(k)}_D = v_D.$$

At this point we have $v_D = g_\text{log}(v_D)$ (otherwise the iteration would not stabilise). Since

$$v_D = g_\text{log}(v_D) = v_0 \log\left( \frac{V - v_D}{R \, i_0} + 1 \right)$$

one can show that this voltag $v_D$ actually satisfies equations (2a) to (2c) simultaneously, i.e. satisfies the diode equation.

Just by repeatedly applying $g_\text{log}$ we obtained a numerical algorithm to solve the diode problem.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£XÆó·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$459361fa-2abd-49ec-aa88-8e37e679c782¹depends_on_disabled_cells§runtimeÎP0µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$a089a707-ff05-4bdb-bd31-1422617388fcŠ¦queued¤logs§running¦output†¤bodyÚÒ

Introduction

Opening remarks

Slides of the presentation on Moodle: These summarise the following paragraphs and the content of the course in a short presentation.

In modern practice every scientist employs computers. Some use them to symbolically derive equations for complex theories, others perform simulations, yet others analyse and visualise experimental results. In all these cases we encounter mathematical problems, which we need to solve using numerical techniques. The point of this lecture is to learn how to formalise such numerical procedures mathematically, implement them using the Julia programming language and analyse using pen and paper why some methods work better, some worse and some not at all.

You might think learning about this is a bit of an overkill and probably not very useful for your future studies. But let us look at a few examples, which give an overview what we will study in more depth throughout the course.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£SÓx·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$a089a707-ff05-4bdb-bd31-1422617388fc¹depends_on_disabled_cells§runtimeÎ ´Üµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$a6c77495-b336-40b2-afaf-184d96b4dce9Š¦queued¤logs‘ˆ¤lineÿ£msg’Úoiter 1: vD = -0.718281828459045 iter 2: vD = 1.999240475732571 iter 3: vD = -481494204.686199128627777 iter 4: vD = 2.000000000000000 iter 5: vD = -485165193.409790277481079 iter 6: vD = 2.000000000000000 iter 7: vD = -485165193.409790277481079 iter 8: vD = 2.000000000000000 iter 9: vD = -485165193.409790277481079 iter 10: vD = 2.000000000000000 ªtext/plain§cell_idÙ$a6c77495-b336-40b2-afaf-184d96b4dce9¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§running¦output†¤body °persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›îÊ¡^·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$a6c77495-b336-40b2-afaf-184d96b4dce9¹depends_on_disabled_cells§runtimeΨ…%µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$079e9f17-27a2-4284-b283-09e6aadbc53bŠ¦queued¤logs§running¦output†¤bodyÚl

Structure of floating-point numbers

As we found out above in practice the set of floating-point numbers is much smaller than the set of real numbers $\mathbb{R}$ and not all numbers can be represented as a floating-point numbers. This leads to the natural question: which numbers can be represented on a computer.

Answering this in all details is beyond the scope of this course (see for example https://teaching.matmat.org/error-control/05_Floating_point_arithmetic.html for more information). However, getting some intuition is helpful to obtain a feeling how large floating-point errors can be.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£V{‰·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$079e9f17-27a2-4284-b283-09e6aadbc53b¹depends_on_disabled_cells§runtimeÎT®µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcfŠ¦queued¤logs§running¦output†¤bodyÚè

Related questions we will discuss:

  • How can I understand whether an obtained numerical answer is credible ?

  • What techniques based on visualisation or plotting help me to understand the accuracy of a numerical algorithm ?

  • How can I understand under which conditions algorithms converge ?

  • If they do not converge, how can I overcome numerical issues ?

  • What are numerically stable techniques for solving standard scientific problems ?

  • How can I understand and evaluate the speed of convergence of an algorithm and improve it even further ?

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Yn¤·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$14ed579e-dc0b-4a3e-87cf-7a2a87de0dcf¹depends_on_disabled_cells§runtimeÎ ýrµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$2255ea65-76a7-403b-af0a-d9dd489b105cŠ¦queued¤logs§running¦output†¤bodyÚr

Clearly far from a handy expression and not the kind of derivative one wants to compute by hand.

So let us compute this derivative numerically instead. An idea to do so goes back to the definition of the derivative $v'(t)$ as the limit $h\to 0$ of the slope of secants over an intervall $[t, t+h]$, i.e.

$$v'(t) = \lim_{h\to 0} \frac{v(t+h) - v(t)}{h}.$$

A natural idea is to not fully take the limit, i.e. to take a small $h > 0$ and approximate

$$\tag{1} v'(t) ≈ \frac{v(t+h) - v(t)}{h}.$$

The expectation is that as we take smaller and smaller values for $h$, this converges to the exact derivatives.

So let's try this at the point t0 = 0.2 for various values for h

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›èÁ¿f·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$2255ea65-76a7-403b-af0a-d9dd489b105c¹depends_on_disabled_cells§runtimeÎfÎãµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80dŠ¦queued¤logs§running¦output†¤bodyÚ°

Representing numbers on a computer

Let us try to shed some light why results in the previous example on numerically computing derivatives get worse and worse as we take smaller stepsizes $h$. For this purpose let us reconsider the expression for approximating the derivative $v'(t)$, which we obtained in (1), namely

$$v'(t) ≈ \frac{v(t+h) - v(t)}{h}.$$

As we saw when $h$ gets smaller this approximation gets worse in practice.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Uhas_pluto_hook_features¬rootassigneeÀ§cell_idÙ$2b2db7e1-fcb8-4012-95c1-ab2a3c83e80d¹depends_on_disabled_cells§runtimeÎܵpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$b192ec68-836c-4fb0-8f03-6ebb01cfcf68Š¦queued¤logs§running¦output†¤bodyÚm

Taking derivatives

Before we dive into the main content of the course, the remainder of this chapter provides some examples for numerical problems and their challenges when solving them numerically. These examples serve to pose motivating questions, which we seek to answer throughout the course.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£T†#·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$b192ec68-836c-4fb0-8f03-6ebb01cfcf68¹depends_on_disabled_cells§runtimeÎ ¿µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$71c91579-a894-44b5-b4d7-f8d98667b977Š¦queued¤logs§running¦output†¤bodyÚP¾ °persist_js_state¤mime©text/html²last_run_timestampËAÚw›å䩆·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$71c91579-a894-44b5-b4d7-f8d98667b977¹depends_on_disabled_cells§runtime͋˵published_object_keys¸depends_on_skipped_cells§erroredÂÙ$5a609e3e-ed94-4e4e-b9e4-c70fd459a25cŠ¦queued¤logs§running¦output†¤bodyÚþ

We first consider the problem of taking derivatives. Derivatives characterise the change of a quantity of interest. E.g. the acceleration as a derivative of the velocity indeed characterises how the velocity changes over time.

More broadly any experiment in physics or engineering operates by imposing a change to a material or chemical system (e.g. changing temperature, pressure, stress etc.) and observing how it reacts.

As a result derivatives are therefore at the heart of physics and engineering and appear everywhere in these subjects. But computing derivatives by hand is not always easy. To see this consider the innocent-looking velocity function.

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£T°…·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$5a609e3e-ed94-4e4e-b9e4-c70fd459a25c¹depends_on_disabled_cells§runtimeÎêµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3Š¦queued¤logs§running¦output†¤body£0.0°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›é³·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$128a93c8-22f3-4102-b6ba-a022939e9fa3¹depends_on_disabled_cells§runtimeÍiµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$ae449fa8-76c9-4d1d-af05-464692436727Š¦queued¤logs§running¦output†¤bodyÚ!

Clearly, the quality of such a fit depends strongly on the polynomial order. Perhaps suprising is, however, that higher degree is not necessarily better. We will discuss why this is.

Related questions we will discuss:

  • How can I fit a parametric model (e.g. the above polynomial) to data points ?

  • How accurate can I expect such a polynomial fit to be ?

  • Can I choose an optimal polynomial order to obtain the most accurate answer ?

  • If I have control over the strategy to acquire data (e.g. how to design my lab experiment), can I have an influence on the accuracy of such interpolations ?

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Z¾·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$ae449fa8-76c9-4d1d-af05-464692436727¹depends_on_disabled_cells§runtimeÎ àSµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$3710d552-729f-4e41-9da2-1756907c4cedŠ¦queued¤logs§running¦output†¤bodyÙ%gexp (generic function with 1 method)°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›îÉZ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$3710d552-729f-4e41-9da2-1756907c4ced¹depends_on_disabled_cells§runtimeΓ µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$7d265705-3ef0-4974-bfcc-ee25707dee1eŠ¦queued¤logs§running¦output†¤body¤true°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›î>\·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$7d265705-3ef0-4974-bfcc-ee25707dee1e¹depends_on_disabled_cells§runtimeÍ1ǵpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$eacbce03-d987-4d20-bc56-815c4f5f4907Š¦queued¤logs§running¦output†¤body…¨elementsÜ!’’©0.0732799ªtext/plain’’ª0.00941812ªtext/plain’’ª0.00666652ªtext/plain’’ª0.00111438ªtext/plain’’ª0.00110504ªtext/plain’’«0.000412217ªtext/plain’’ª6.06921e-5ªtext/plain’’ª8.47159e-6ªtext/plain’ ’ª3.70204e-7ªtext/plain’ ’ª5.57174e-6ªtext/plain’ ’ª3.70204e-7ªtext/plain’ ’©1.2995e-7ªtext/plain’ ’ª7.38851e-8ªtext/plain’’ª7.72871e-8ªtext/plain’’ª3.31346e-7ªtext/plain’’ª1.06383e-6ªtext/plain’’ª3.37003e-6ªtext/plain’’ª1.06567e-5ªtext/plain’’ª3.36972e-5ªtext/plain’’«0.000106555ªtext/plain’’«0.000336912ªtext/plain’’ª0.00106496ªtext/plain’’©0.0033632ªtext/plain’’©0.0105904ªtext/plain’’©0.0330401ªtext/plain’’©0.0999968ªtext/plain’’§0.27175ªtext/plain’’§0.43197ªtext/plain’’§2.01277ªtext/plain’’§9.92701ªtext/plain’’§266.047ªtext/plain’ ’©2.19432e7ªtext/plain’!’ª1.27727e11ªtext/plain¬prefix_short ¨objectid°eb5bfd9f84b6c528¦prefix§Float64¤type¥Array°persist_js_state¤mimeÙ!application/vnd.pluto.tree+object²last_run_timestampËAÚw›èÖ.·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$eacbce03-d987-4d20-bc56-815c4f5f4907¹depends_on_disabled_cells§runtimeÎÄ8ëµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$ac1a0435-6447-45fc-97b6-475e8586eebdŠ¦queued¤logs§running¦output†¤bodyÙS(::Main.var"workspace#5".var"#Sidebar#Sidebar##0") (generic function with 1 method)°persist_js_state¤mimeªtext/plain²last_run_timestampËAÚw›ï£Ö·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$ac1a0435-6447-45fc-97b6-475e8586eebd¹depends_on_disabled_cells§runtimeÎ,äáµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31aŠ¦queued¤logs§running¦output†¤bodyÚÜ

As we will see in the next lectures there are a number of numerical techniques to solve such nonlinear fixed-point problems $g(x) = x$. Each of these have their advantages and disadvantages and hardly any of them just work.

Let us also note already here that fixed-point problems are closely related to root-finding problems (frz. trouver des zéros). Namely if $x$ is a fixed-point of $g$ than it is a root of $f(x) = g(x) - x$.

Often for a scientific problem there are many choices how to formulate it as a fixed-point or root-finding problem. Therefore there are usually many choices how to solve the same problem on a computer. As we saw above not all of these options work equally well.

This immediately raises some questions:

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›£Y;·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$a7d19874-4e01-4b0c-bd5b-07bee478d31a¹depends_on_disabled_cells§runtimeΡ¯µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6Š¦queued¤logs§running¦output†¤bodyÚ–

t0 = 0.2

°persist_js_state¤mime©text/html²last_run_timestampËAÚw›èº$æ·has_pluto_hook_features¬rootassigneeÀ§cell_idÙ$45a70a4c-549d-4c43-9ccc-814c9e5a8ee6¹depends_on_disabled_cells§runtimeÎÍoŽµpublished_object_keys¸depends_on_skipped_cells§errored©shortpath²01_Introduction.jl®last_save_timeËAÚw›£O3Ó«in_temp_dir¨metadata€