Hot answers tagged

41

To understand why this is a good approximation note that $(\sqrt{x})' = \frac{1}{2\sqrt{x}}$. So the formula is of the form $f(x) = f(y) + f'(y)(x-y)$. See Taylor's theorem for more details.


33

For a purely algebraic and non-calculus derivation, use the fact that $$x - y \; = \; (\sqrt{x} + \sqrt{y})(\sqrt{x} - \sqrt{y}),$$ then replace $\;\sqrt{x} + \sqrt{y}\;$ with $\;\sqrt{y} + \sqrt{y} = 2\sqrt{y}\;$ (since we are assuming $\sqrt{x}$ is approximately equal to $\sqrt{y})$ to obtain the approximation $$x - y \; \approx \; 2\sqrt{y} \left( \...


16

As presented there that would be "Newton's method." But it is older than Newton. It really is "the Babylonian" method. The Babylonian method: If you are looking for $\sqrt n$, take a guess and pulg it into: $x_{k+1} = \frac 12 (x + \frac n{x_k})$ If you guess is close is close to $\sqrt{n}, \frac n{x_k}$ will will also nearly equal $\sqrt n$, but with ...


8

\begin{align} \sqrt{x} &= \sqrt{y + x - y}\\ &= \sqrt{y}{\left(1 + \frac{x-y}{y}\right)}^{1/2}\\ &\approx \sqrt{y}\left(1 + \frac{x-y}{2 y}\right)\\ &= \sqrt{y} + \frac{x-y}{2 \sqrt{y}} \end{align} In going from the second to the third line above, I have used the Taylor series $\sqrt{1 + z} = 1 + \frac{z}{2} + O\left(z^2\right)$. In fact ...


7

$$\log_{10}(e^{-10000}) = -10000 * (0.4342944819) = -4342.944819$$ Thus, $$e^{-1000}=10^{ -4342.944819} = 10^{-4343} 10^{ 0.05518} = 1.13548386531 \times 10^{-4343}$$


4

We may as well suppose that $y_0^2 < x < (y_0+1)^2$ for some integer $y_0$. It isn't that hard to show that $y_0 < \sqrt x < \dfrac {x}{y_0} < y_0+1$. So we can replace $\sqrt x \in (y_0, y_0+1)$ with $\sqrt x \in \left(y_0, \dfrac {x}{y_0} \right)$. Which is a smaller interval. Your algorithm chooses the next approximation, $y_1$, to be the ...


3

As you appear to be using the bisection method you should have: Step1 a=-2, b=-1, c=-1.5; f(a)=-23, f(b)=+2, f(c)=-2.0938 Step2: a=-1.5, b=-1, c=-1.25; f(a)=-2.0938, f(b)=+2, f(c)=1.0732 Step3: a=-1.5, b=-1.25, c=-1.375; f(a)=-2.0938, f(b)=+1.07324, f(c)=-0.13364 So we now have the root is in the interval $(-1.375,-1.25)$ and the mid point of this ...


3

This is not a solution but approximation. First, note that $\frac{3}{8}=0.3750000000$. The function $f(x)=x^x(1-x)^{2x}$ is convex on $(0,c_1)\cup(c_2,1)$ and concave on $(c_1,c_2)$, where $c_1\approx 0.2718247$ and $c_2\approx 0.5243816$. So that applying the hermite-hadamard inequality \begin{eqnarray} f\left( {\frac{{a + b}}{2}} \right) \le \frac{1}{{b ...


2

$$K_\nu(x)=\int_{0}^{+\infty}\cosh(\nu t)\exp(-x\cosh t)\,dt = \frac{\pi}{2\sin(\nu \pi)}\left(I_{-\nu}(x)-I_{\nu}(x)\right)$$ together with the $\phantom{}_2 F_1$ representations: $$ I_\nu(x) = \frac{1}{\Gamma(1+\nu)}\left(\frac{x}{2}\right)^{\nu}\left\{1+\frac{(x/2)^2}{1(1+\nu)}\left(1+\frac{(x/2)^2}{2(2+\nu)}\left(1+\frac{(x/2)^2}{3(3+\nu)}\left(1+\ldots\...


2

I think using the central limit theorem is a good approach, but you can also use Hoeffding's inequalities to get a bound that's easier to compute. As mentioned in the other answer, it's wise to approximate with a Binomial distribution since $2^{105}$ is much larger than $2^{95}$. I'm going to start out without this assumption though to illustrate how good ...


2

You have $$ (1-10^{-1014})^{10^{155}} = e^{10^{155}\ln(1-10^{-1014})} \simeq e^{-10^{155}\cdot 10^{-1014}} = e^{-10^{-859}} \simeq 1-10^{-859} $$ using the low-order Taylor expansions $\ln(1+u) = u +o(u)$ and $e^u = 1+u+o(u)$ when $u\to 0$. Another approach, using $(1+u)^n = 1+nu + o(u)$ for fixed $n$ and $u\to 0$ (which is a valid approximation as $"nu" ...


1

The general formula for $f:\mathbb{R}^n \to \mathbb{R}$ at ${\bf{x}}={\bf{x}}_0$ is $$f({\bf{x}})=f({\bf{x}}_0)+\nabla f({\bf{x}}_0) \cdot ({\bf{x}}-{\bf{x}}_0) + \frac{1}{2} ({\bf{x}}-{\bf{x}}_0) \cdot \nabla \nabla f ({\bf{x}}_0) \cdot ({\bf{x}}-{\bf{x}}_0) + \cdot \cdot \cdot$$ If you call ${\bf{x}}-{\bf{x}}_0={\bf{y}}$ then the above formula can be ...


1

By dichotomy, every iteration halves the uncertainty. Hence four iterations will be enough, requiring six function evaluations (five if the presence of a root is guaranteed in the initial interval). $f(-2)=-23<0,f(-1)=2>0\implies x\in(-2,-1),$ $f(-\frac32)=-2.09375<0\implies x\in(-\frac32,-1),$ $f(-\frac54)=1.07324>0\implies x\in(-\frac32,-\...


1

We can use Newton's method $$x_{k+1} = x_k - \dfrac{f (x_k)}{f' (x_k)} = x_k - \dfrac{x_k^5 + 2 x_k^2 + 1}{5 x_k^4 + 4 x_k}$$ with initial guess, say, $x_0 = -2$. In Haskell: λ take 10 $ iterate (\x->x-(x**5+2*x**2+1)/(5*x**4+4*x)) (-2) [-2.0,-1.6805555555555556,-1.4768055489926624,-1.383795516323458,-1.364705763354018,-1.363965683835678,-1....


1

Your function is just the Fourier transform of the "triangle function" (Heaviside Lambda) $$ f(x) = \left(1-\left|x\right|\right)\cdot\mathbb{1}_{(-1,1)}(x) $$ that is compact supported. By the Paley-Wiener theorem, $\widehat{f}$ is an entire function: since it is not constant (by just comparing the behaviour at $0$ and at $\pm\infty$), it cannot be constant ...


1

Your first result is incorrect, and you seem to be using $S_n$ to mean different things in your results. The statement of the Central Limit Theorem is for $S_n$ the sum of $n$ iid random variables with mean $\mu$ and standard deviation $\sigma$. It is true from the CLT that $$\lim_{n\to\infty}\mathbb{P}\left(\frac{\frac{S_n}{n}-\mu}{\sigma/\sqrt{n}}\leq z\...


1

Before his edit Pretty sure it only works for functions $p(n)=o(1)$ (using little-$o$ notation). Otherwise, $p(n)=\Omega(1)$, so $1-(1-p(n))^n=\Omega(p(n)^n)$. Assuming $p \rightarrow \infty$, we know $\frac{p(n)^n}{np(n)} \rightarrow \infty$. After his edit I found that for my ratio, $p(n) \sim n^{\frac{1}{n-1}}$ yields $p^n \sim np$. However, it's ...


1

Slugger's answer is perfectly correct. A slightly different way of thinking about the problem has been useful to me in past. Let us restate the problem as follows. Let $\theta_0 \in \mathbb{R}$ be fixed and consider the problem of computing $y = y(t)$, such that $$ \label{main}\tag{1} y(t) + t \sin y(t) = \theta_0, $$ Here $t$ plays the role of $\epsilon$ ...


1

Use a series expansion for the $\sin$ term. You can truncate it and collect the terms according to the power of $\epsilon$ and then solve.


1

About the main problem, since $$ \int_{0}^{1} e^{x}\,dx = (e-1), \qquad \int_{0}^{1} e^{x} P_1(2x-1)\,dx = (3-e) $$ the best $L^2$ approximation is given by $\color{red}{(4e-10)+(18-6e)x}$ as already pointed by Winther in the comments. About $(a)$ and $(b)$, given the convexity of $e^x$ it is quite trivial that the best $L^1$ and $L^\infty$ approximations ...


1

(a.) I would assume that $l(x)$ is going to intersect $y = e^x$ at two points, $0 < u < v < 1$. In which case \begin{align} l(x) &= \dfrac{e^v - e^u}{v - u}(x - u) + e^u \\ &= m x + b\\ \hline \text{Where} \\ & m = \dfrac{e^v - e^u}{v - u}\\ & b = \dfrac{v e^u - u e^v}{v - u}\\ \end{align} Then I would ...


1

I'm not sure why there is a $(-2+\gamma+\ln 2)$, because $\left|\ln(x+1) - \Psi(x+\frac32)\right| < 0.0365$ itself is already satisfied. The approximation comes from the series expansion of $\exp\left(\Psi(x+\frac12)\right)$, which states, for $x > 1$, \begin{align} \Psi\left(x + \frac12\right) = \ln\left( x + \frac{1}{4!\cdot x} - \frac{37}{8\cdot 6!...


1

For large $n$, $n2^{-n/2}<<1$ so the $e^{-x}\approx 1-x$ approximation works. Let's replace $7$ with $k$. We have $$\ln f = n^k\ln\left(1-\left(1-2^{-n/2}\right)^n\right)\approx n^k\ln\left(n2^{-n/2}\right)=n^k\left(-n\ln\sqrt{2}+\ln n\right).$$Hence$$f\approx n^{n^k}\sqrt{2}^{-n^{k+1}}.$$


1

Proof that Newton's method converges is a standard and elementary result that can be found in any textbook on numerical analysis, as well as in any number of places online (including Wikipedia or Pete Clark's excellent notes). The real interesting observation, though, is that Newton's method work a lot better in practice than is guaranteed by the theory. ...


1

Since $2^{95}$ is small compared to $2^{105}$, we can make the approximation that we are sampling with replacement: let $$X_1,...,X_n \overset{iid}{\sim}\text{Bernoulli}(p)$$ where $n=2^{95}$, $p=\frac{1}{20}$. Then their sample mean $\bar{X}:=\frac{1}{n} \sum_{i=1}^n X_i$ has mean and variance: $$E(\bar{X})=p, \sigma^2 := Var(\bar{X})=\frac{p(1-p)}{n}$$ ...



Only top voted, non community-wiki answers of a minimum length are eligible