⛏️

# Prerequisites

• Single variable calculus.
• Linear algebra.
• Algorithms

# Introduction

Approximation of Real number to some procession.

Pay for precision with time.

# Key questions

## Numerical analysis, numerical methods, or symbolic calculation

#### Differences

NameDifferencesSimilarities
Numerical analysisProofRigorousnumerical methodsAlgorithms
Numerical methodsAlgorithms
Symbolic calculationDeductive

# Story

William Kahan

https://mathshistory.st-andrews.ac.uk/Biographies/Seidel/

# Glosario

Modelo matemático. Descripción de un sistema (fenómeno, procedimiento, procedimiento …) usando la teoría (gramatica, principios, sus reglas) de alguna de las áreas de las matemáticas (análisis numérico, ecuaciones diferenciales, teoría de automatas, probabilidades, topología, …) .

Exactitud. Cualidad de conocimiento sobre la magnitud real.

Precision.  Dispersión del conjunto de valores obtenidos o medidos de un instrumento.

Sesgo o inexacitud. Diferencia entre la magnitud real y los valores obtenidos.

Incertidumbre o imprecision. Dispersión tendiendo a cero de los valores obtenidos de un instrumento.

Accuracy and precision

Bias.

ISO 5725-1 ISO/DIS 5725-1

# Mathematical preliminaries and Error Analysis

## 1.1 Review of Calculus

### Worked examples

1. Show that the following equations have at least one solution in the given intervals.
• $xcos(x)-2x^2+3x-1=0,[0.2,0.3]\text{ and }[1.2,1.3]$﻿

As $f(x)=xcos(x)-2x^2+3x-1$﻿ is continuous and

$K=0$﻿,

The Intermediate Value Theorem implies that a number x exists, with $0.2﻿.

If $f\in C[1.2,1.3]$﻿ and 0 is a number between $f(1.2)=0.1548$﻿ and $f(1.3)=-0.1322$﻿, then there exists a number $c$﻿ in $(1.2,1.3)$﻿ for which $f(c)=0$﻿.

1. Find intervals containing solutions to the following equations.
• $x-3^{-x}=0$﻿

## 1.2 Round-off Errors and Computer arithmetic

Def. Floor function

Def. Chopping or truncating is a function such that

Def. Suppose that $p^*$﻿ is an approximation to $p$﻿.

## Ceil and floor

https://stackoverflow.com/questions/6208488/implementation-of-ceil-and-floor

## Cast

https://stackoverflow.com/questions/22330575/how-are-typecasts-in-c-implemented

https://en.wikipedia.org/wiki/Loop_unrolling

## How Many Decimals Do We Really Need?

Floating-Point Computation by Pat Sterbenz

• IEEE 754

## How calculating more precise than double or long double? How to increase precision by hundreds of decimals?

Leijen, Daan (December 3, 2001). "Division and Modulus for Computer Scientists" (PDF). Retrieved 2014-12-25.

# How can minimize the error upon arithmetic operations?

• Minimize the number of arithmetic calculations.
• Polynomials should always be expressed in the nested form before performing an evaluation.
• Use rounding over chopping.
• Prioritize the operations by error-producing sum, multiplication, and division.

### Worked examples

1. Determine the six-digit a) chopping and b) rounding values of the $\phi,e$﻿.

## Chapter notes

https://nptel.ac.in/content/storage2/courses/122104019/numerical-analysis/Rathish-kumar/numerr/new4.htm

# Solutions of Equations in One Variable

Is there any way to find the number of real roots of a polynomial computationally?

## Worked examples

1. Da la definicion de numero de maquina en la forma de punto flotante decimal normalizado.

Sea el punto flotante decimal normalizado analogo al punto flotante binario normalizado para representar las operaciones de los numeros de maquina segun el IEEE754 en base 10 y siendo inspirado en la normalizacion de la notacion cientifica (aqui tomamos $d_0=0$﻿), a saber, el punto flotante decimal normalizado tiene la forma:

donde $d_1$﻿ es distinto de 0 ($d_1\in N \text{ tal que }1\le d_1\le9$﻿) y los siguientes terminos del significando o mantisa $d_i$﻿ son cualquier numero menor a la base 10 ($d_i \in N \text{ tal que } 0\le d_i \le 9 \lor2\le i\le k$﻿), 10 es nuestra base $b$﻿, $n$﻿ el expontente y $k$﻿ digitos decimales del numero de maquina tal que

$\pm(d_0+d_110^{-1}+...+d_{k-1}10^{-k+1})10^{n}=y,y\in R$﻿

Ejemplo:

$y=10.15$﻿

$normalize(y)=0.1015\times10^2$﻿

porque

$(0+1\times10^{-1}+0\times{10^0}+1\times10^{-2}+5\times10^{-3})\times10^{2}=$﻿

$10+0+0.1+0.5=10.15$﻿

2.a

Si $lim_{x\to0}xcosx-sinx=lim_{x\to0}x-sinx=0$﻿,

entonces por regla de L’Hopital (*)

Si $lim_{x\to0}-xsinx=lim_{x\to0}1-cosx=0$﻿,

entonces por *

2. b

Redondeo a 4 digitos.

$f(0.1000\times 10^0)\\=\dfrac{(0.1000\times 10^0)cos(0.1000\times 10^0)-sin(0.1000\times 10^0)}{(0.1000\times 10^0)-sin(0.1000\times 10^0)}\\ =\dfrac{(0.1000\times 10^0)(0.9950\times10^0)-(0.9983\times10^{-1})}{(0.1000\times 10^0)-(0.9983\times10^{-1})}\\ =\dfrac{(0.9950\times 10^{-1})-(0.9983\times10^{-1})}{0.1669\times10^{-3}}\\ =\dfrac{-0.3300\times10^{-3}}{0.1669\times10^{-3}}\\ =-0.1977\times10^{1}$﻿

2.c

$cos(0.1000\times 10^0)=(0.1000\times10^0)-\dfrac{(0.1000\times10^0)^2}{(0.2000\times10^1)}+O(x^4)=\\ (0.1000\times10^0)-\dfrac{(0.1000\times10^{-1})}{(0.2000\times10^1)}+O(x^4)=\\ =(0.1000\times10^0)-(0.5000\times10^{-2})+O(x^4)\\ =0.9950\times10^{0}+O(x^4)$﻿

$sin(0.1000\times10^0)=(0.1000\times10^0)-\dfrac{(0.1000\times10^0)^3}{0.6000\times 10^1}+O(x^5)\\ = (0.1000\times10^0)-\dfrac{(0.1000\times10^{-2})}{0.6000\times 10^1}+O(x^5)=\\ (0.1000\times10^0)-(0.1667\times10^{-3})+O(x^5)= (0.9983\times10^{-1})+O(x^5)$﻿

1. d

2.e

1. Usa el metodo de Steffensen para encontrar una aproximacion a la raiz de

con $p_0 = −1$﻿, $TOL = 1 \times 10^{−5}$﻿ y usa al menos 10 digitos en los calculos.

Vas a poner las formulas o ecuaciones que usaste en cada uno de los calculos aritmeticos que realizaste.

1. Find root of a number using Newton’s method

https://opensource.apple.com/source/Libm/Libm-47.1/ppc.subproj/sqrt.c.auto.html

https://math.mit.edu/~stevenj/18.335/newton-sqrt.pdf

https://math.stackexchange.com/questions/296102/fastest-square-root-algorithm

https://stackoverflow.com/questions/63450864/ieee-754-conformant-sqrt-implementation-for-double-type

Tabla comparativa

 Metodo Diferencias Ventajas Desventajas Biseccion Basado en el teorema del valor intermedio, determinando cualquier intervalo lo satisface hasta lograr la tolerancia deseada. Por tanto, necesita un intervalo [a,b]. @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$a=1$﻿ El mas simple de implementar.No necesita calculo de derivada.Siempre converge a la raiz. El mas lento por su radio de convergencia.No encuentra raices complejas.Buenas aproximaciones pueden ser rechazadas. Netwon-Rapshon Metodo de punto fijo, que necesita del calculo de la derivada. Necesitando un punto @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$p_0$﻿ como entrada. @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$a=2$﻿ siempre que M= El mas rapido, su radio de convergencia es@import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$a=2$﻿ Necesita calculo previo de derivada.No encuentra raices complejas.@import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$f’(x)=0$﻿ el metodo diverge.Depende en gran medida de @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$p0$﻿ para converger (no esta en el intervalo@import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$[p-\delta, p+\delta]$﻿) Secante Metodo de punto fijo, que NO necesita del calculo de la derivada, usando su aproximacion mediante la def. Necesitando dos puntos de la secante @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$p_0,p_1$﻿ como entrada. @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$a=\phi$﻿ No necesita calculo de derivada. No encuentra raices complejas.Puede diverger. Regula falsi Adaptacion del metodo de la secante y biseccion que asegura que la raiz este en el intervalo @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$[p_0,p_1]$﻿.@import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$a=1$﻿ No necesita calculo de derivada. No encuentra raices complejas.No es recomendado por (Burden, 73). Müller Basado en metodo de la secante, pero en vez de una linea usamos una parabola, por tanto, necesitamos 3 puntos. @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$p_0,p_1,p_2$﻿. @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css')$a=1.87$﻿ No necesita calculo de derivada.Calcula raices complejas. Puede diverger. Halley Householder-n

http://www.math.usm.edu/lambers/mat460/fall09/lecture7.pdf

https://math.stackexchange.com/questions/2473794/asymptotic-order-versus-order-of-convergence

https://math.stackexchange.com/questions/976942/whats-the-formal-difference-between-analytical-and-numerical?rq=1

# Interpolation

https://github.com/sanchezcarlosjr/uabc/blob/main/essays/numerical-analysis/uabc_MA_Interpolaci_n_por_el_m_todo_de_diferencias_divididas_de_Newton.pdf

https://gist.github.com/sanchezcarlosjr/6cd5f027740e964c4a45cb0880dc18ae

https://gist.github.com/sanchezcarlosjr/74ab156989087338a6d27227817a7a22

Kochanek–Bartels spline

Bezier curves

https://docs.scipy.org/doc/scipy/tutorial/interpolate.html

# Numerical linear algebra

## Solving Linear Systems

### Approximate solutions by iterations

Exact solutions tend to be inefficiency $O(n^3)$﻿. Our computers save us by their power processing in complex calculations. Thus the methods were born.

We say that a method approximate to the solution $x$﻿ from an arbitrary initial vector $x^{[0]}$﻿ where each k iteration tend to $x^{[0]},x^{[1]},x^{[2]},...,x^{[k]},...\rarr x$﻿ such that $Ax=b$﻿.

The method converges when $lim_{k\rarr \infty} x^{[k]}=x$﻿, otherwise it diverges.

### Jacobi method

This method was discovered by Carl Gustav Jacob Jacobi, which use triangular matrices.

https://sci-hub.do/https://doi.org/10.1080/0020739980290204

https://arxiv.org/pdf/1304.2097.pdf

### Seidel method

This method was discovered by Philipp Ludwig von Seidel. We now (inappropriately) call the Gauss-Seidel method [1], which improves the Jacobi method. Honor to whom honor is due.

## SVD

https://cims.nyu.edu/~donev/Teaching/NMI-Fall2014/Lecture5.handout.pdf

# Elementary function computations

For computations with very high precision, the algorithms based on the elliptic integrals are among the fastest known today for the logarithm, the number π, and the exponential function.

Logarithms, pow, gamma,

### Notes

CORDIC

https://www.jjj.de/fxt/fxtbook.pdf

# Numerical differential equations

https://gist.github.com/sanchezcarlosjr/80aa8c039d71bea3decc86fb744f719f

Los métodos más comunes para resolver este tipo de problemas incluyen el método de las diferencias finitas, el método de los elementos finitos, y el método de Runge-Kutta.

## Log

1. Count the number of digits

By mod. Its time complexity is $O(n)$﻿

def algorithmMod(n):
count=0
while(n>0):
count=count+1
n=n//10
return count

By log. Its time complexity is $O(1)$﻿

def algorithmLog(number):
return math.floor(math.log10(math.abs(number)))+1

https://replit.com/join/zpwivezz-carlossanchez14

## Modulo operation

Remainder after division.

### Worked examples

1. Extracting individual digits.

# Rounding

Round half to even, a variant of the round-to-nearest method.

This method is called the round-to-even method. Other names include the round-half-to-even method, the round-ties-to-even method, and "bankers' rounding." This variant of the round-to-nearest method is also called convergent rounding, statistician's rounding, Dutch rounding, Gaussian rounding, odd–even rounding, or bankers' rounding.

Banker's rounding: the value is rounded to the nearest even number. Also known as "Gaussian rounding", and, in German, "mathematische Rundung".

Standard rounding: the value is rounded to the nearest number (be it odd or even). In German it is known as "kaufmännische Rundung".

754-2019 - IEEE Standard for Floating-Point Arithmetic since 1985.

https://en.wikipedia.org/wiki/Rounding

If the fractional part of x is 0.5, then y is the even integer nearest to x.

function roundIt(n, d = 0) {
var m = Math.pow(10, d);
var n = +(d ? n * m : n).toFixed(8);
var i = Math.floor(n),
diff = n - i; // getting the difference
var e = 1e-8; // Rounding errors in var(diff)
// Checking if the difference is less than or
// greater than, based on that adding the 1 to it.
var r = (diff > 0.5 - e && diff < 0.5 + e) ?
((i % 2 == 0) ? i : i + 1) : Math.round(n);
return d ? r / m : r; // if d != 0 then returning r/m else r
}

https://www.geeksforgeeks.org/gaussian-bankers-rounding-in-javascript/

## Experimental

import time
import numpy as np

def timer(f):
x=np.random.rand(1,100000)[0]
times = []
for i in range(10):
tic = time.perf_counter()
f(x)
toc = time.perf_counter()
times.append(toc - tic)
print(f"Build finished in {np.mean(times):0.4f} +- {np.std(times):0.4f} seconds")

## Seminumerical Algorithms. Arithmetic.

Numerical analysis.

# References

Burden, R. L. y Faires, J. D. (2015). Análisis numérico. (9a ed.).
Cengage Learning.

Chapra, S. C. (2017). Applied numerical methods with MATLAB for engineers and scientists. (4a ed.). Mcgraw-Hill Education.

Demanet, L., (2012). Introduction to numerical analysis. MIT
opencourseware.
https://ocw.mit.edu/courses/mathematics/18-330introduction-to-numerical-analysis-spring-2012/

Epperson, J. F., (2021). An introduction to numerical methods and analysis. (3a ed). Wiley.

Gezerlis, A., (2020). Numerical methods in physics with python. Cambridge University Press.

Howard II, J. P., (2020). Computational methods for numerical analysis with R. CRC Press

Fausett, L.V. (2002). Numerical methods: algorithms and applications. Pearson.

Gerald, C.F. y Wheatley, P.O. (2001). Análisis numérico con aplicaciones (6a ed.). Prentice Hall.

Stoer, J. & Bulirsch, R. (1993). Introduction to numerical analysis.Springer-Verlag.