\documentclass[12pt]{article}
% This first part of the file is called the PREAMBLE. It includes
% customizations and command definitions. The preamble is everything
% between \documentclass and \begin{document}.
\usepackage[margin=1in]{geometry} % set the margins to 1in on all sides
\usepackage{graphicx} % to include figures
\usepackage{amsmath} % great math stuff
\usepackage{amsfonts} % for blackboard bold, etc
\usepackage{amsthm} % better theorem environments
\usepackage[english]{babel}
\usepackage{comment}
\newcommand{\forceindent}{\leavevmode{\parindent=1em\indent}}
% various theorems, numbered by section
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\DeclareMathOperator{\id}{id}
\newcommand{\bd}[1]{\mathbf{#1}} % for bolding symbols
\newcommand{\RR}{\mathbb{R}} % for Real numbers
\newcommand{\ZZ}{\mathbb{Z}} % for Integers
\newcommand{\col}[1]{\left[\begin{matrix} #1 \end{matrix} \right]}
\newcommand{\comb}[2]{\binom{#1^2 + #2^2}{#1+#2}}
\begin{document}
\title{Newton's Method Cycles}
\author{Edgar Vanoye \& MacKay Martin\\
Department of Mathematics\\
450 S. Easton Road\\
Arcadia University\\
Glenside, PA 19038}
\date{\today}
\maketitle
\nocite{*}
\begin{abstract}
\noindent Based on the paper \textit{Sometimes Newton's Method Cycles} \cite{Sometimes}, we first asked ourselves if there were any Newtonian Method Cycle functions which have non-trivial guesses. We encountered a way to create functions that cycle between a set number of points with any initial, non-trivial guesses when Newton's Method is applied. We exercised these possibilities through the methods of 2-cycles, 3-cycles and 4-cycles. We then generalized these cycles into k-cycles. After generalizing Newton's Method, we found the conditions that skew the cycles into a spiral pattern which will either converge, diverge or become a near-cycle. Once we obtained all this information, we explored additional questions that rose up from our initial exploration of Newton's Method.
\end{abstract}
\newpage
\section{Introduction}
\subsection{Newton's Method}
Newton's Method\footnote{This function is meant to be used in iteration.}, also known as the Newton-Raphson method, is a root-finding algorithm that works by getting successively better approximations to the roots of real-valued functions. The method in one variable is used as follows:\\
\newline
The method starts with a function $f$ defined over the real numbers $x$, the function's derivative $f'$, and an initial guess $x_0$ for a root of the function $f$. If the function satisfies the assumptions made in the derivation of the formula and the initial guess is close, then the manner in which Zaytman \cite{Zaytman} presents a better approximation for $x_1$ is
$$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$
\newline
Geometrically, $(x_1, 0)$ is the intersection with the $x$-axis of the tangent to the graph of $f$ at $(x_0, f(x_0))$. The process that Zaytman \cite{Zaytman} presented is repeated as
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
\newline
until a sufficiently accurate value is reached.
\subsection{History}
Newton's Method is derived from Isaac Newton's description of a special case of the method in "On Analysis by Equations with an infinite number of terms" (written in 1669 and published in 1671 by William Jones)\cite{Newton's}. Newton applied the method only to polynomials. He does not compute the successive approximations $x_n$, but computes a sequence of polynomials, and only at the end arrives at an approximation for the root $x$. Newton viewed the method as purely algebraic and makes no mention of the connection with calculus. Newton's method was first published in 1685 in \textit{A Treatise of Algebra both Historical and Practical} by John Wallis. In 1690, Joseph Raphson published a simplified description in \textit{Analysis aequationum universalis}. Raphson again viewed Newton's method purely as an algebraic method and restricted its use to polynomials, but he describes the method in terms of the successive approximations $x_n$ instead of the more complicated sequence of polynomials used by Newton. Finally, in 1740, Thomas Simpson described Newton's method as an iterative method for solving general nonlinear equations using calculus, essentially giving us the use described above.
\subsection{How Newton's Method Behaves}
Before we use Newton's Method, we must understand what outcomes we should get from using this formula. There are two ways that Newton's Method behaves -- converge and diverge. When a function converges, the roots of the function will be found for the unknown variable. There are, however, different ways in which the method can fail:
\begin{enumerate}
\item If the first derivative is not well behaved in the neighborhood of a particular root, the method may overshoot and diverge from that root.
\item If a critical point of a function is encountered, the derivative will be zero and the method cannot be used because of division by zero. \item If there is a large error in the initial estimate then it may contribute to non-convergence of the algorithm.
\item The algorithm cycles between a set number of points, never reaching the root.
\end{enumerate}
In this paper we will focus on how Newton's Method fails by cycling. There are also many different ways for Newton's Method to cycle, such as 2-cycle, 3-cycle, 4-cycle. This pattern continues for any k-cycle. \\
\newline
\noindent To use the method, we start with an initial guess which is reasonably close to the true root, then the function is approximated by its tangent line and one computes the x-intercept of this tangent line, which is easily done with elementary algebra. This x-intercept will typically be a better approximation to the function's root than the original guess, and the method can then be iterated.
\newline
\noindent As stated above, one of the ways that Newton's Method behaves is by converging. Where the formula continually finds a more accurate number of the true root through iteration. Here is an example from a video \cite{video} demonstrating when Newton's Method converges.
$$
x^2 - 4 = 2x - 3
$$
$$
x^2 - 2x - 1 = 0
$$
$$
h(x) = x^2 - 2x - 1
$$
$$
h'(x) = 2x - 2
$$
$$
\text{True root } x = 1 - \sqrt[]{2} \approx -0.4142136
$$\\
$$
x_1 = 0
$$
\begin{align*}
x_2
&= 0 - \frac{0^2 - 2 \cdot 0 - 1}{2(0) - 2}\\
&= - \frac{-1}{-2}\\
&= - \frac{1}{2}
\end{align*}
\begin{align*}
x_3
&= -\frac{1}{2} - \frac{(-\frac{1}{2})^2 - 2(-\frac{1}{2}) - 1}{2(-\frac{1}{2}) - 2}\\
&= -\frac{1}{2} - \frac{\frac{1}{4} +1 - 1}{-1 - 2}\\
&= -\frac{1}{2} - \frac{\frac{1}{4}}{-3}\\
&= -\frac{6}{12} - \frac{1}{-12}\\
&= -\frac{5}{12} \\
&\approx -0.41667
\end{align*}
\noindent The second way that Newton's Method behaves is in the instance that a function does not converge. We will focus on non-convergence by cycling and the ways in which Newton's Method can cycle are very similar, but they all have one difference: they all cycle between the number of points that is in the name. For example, 2-cycle has two points it cycles between, $x_0$ and $x_1$, then repeats in a loop using only these two points. For 3-cycle and 4-cycle, they do the same thing as 2-cycles, but 3-cycle loops between 3 points $(x_0, x_1, x_2)$ and 4 points $(x_0, x_1, x_2, x_3)$ for 4-cycles. k-cycles loops between k points $(x_0, x_1, \ldots, x_{k-1})$. k is an undetermined number of cycles. Here is an example of a 2-cycle.
\begin{align*}
f(x) &= x^3 - 2x + 2, \forceindent \forceindent x_0 = 0
\end{align*}
\begin{align*}
x_1
&= 0 - \frac{0^3 - 2(0) +2}{3(0)^2 - 2}\\
&= 1
\end{align*}
\begin{align*}
x_2
&= 1 - \frac{1^3 - 2(1) +2}{3(1)^2 - 2}\\
&= 0
\end{align*}
\subsection{Dynamical Systems}
\noindent Unlike iterative processes where time is measured in discrete intervals such as years or generations, differential equations are examples of continuous dynamical systems wherein time is a continuous variable \cite{Chaos}. Unlike functions that converge that do not change, dynamics is the study of change. Dynamical system is how a system of variables interacts and changes with time. It can be used to answer questions about the economy, the stock market, simplified climate models, reactive or radioactive chemicals in groundwater, etc. In general, the rates of change will depend on the values of the other variables and this is what makes dynamical systems interesting. For the most part, applications fall into three broad categories: predictive (also referred to as generative), in which the objective is to predict future states of the system from observations of the past and present states of the system, diagnostic, in which the objective is to infer what possible past states of the system might have led to the present state of the system (or observations leading up to the present state), and, finally, applications in which the objective is neither to predict the future nor explain the past but rather to provide a theory for the physical phenomena. These three categories correspond roughly to the need to predict, explain, and understand physical phenomena.
\section{Newton's Method Cycling}
\subsection{2-cycles}
In this paper, a method for finding a 2-cycle with symmetry was employed on simplified discreet dynamical systems. For higher order cycles, they found that complex powers of x are needed and that all functions cycle symmetrically.\\
\newline
Consider applying Newton's Method to $f(x) = x^p$
\begin{align*}
x_{n+1} &= x_n - \frac{{x_n}^p}{p \cdot {x_n}^{p-1}}\\
&= \left(1 - \frac{1}{p}\right)x_n
\end{align*}
To find 2-cycles we use $p = \frac{1}{2}$ to obtain
$$
x_{n+1} = -x_n
$$
\noindent
This will give us a function that will alternate any initial guess with its negative counterpart.
Given this condition and applying it to Newton's Method, here we solve for an equation that guarantees a symmetrical 2-cycle:
$$
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = -x_n
$$
\newpage
Replace any $f(x_n)$ with $y$ and $x_n$ with $x$ to create a differential equation that can be easily solved\\
\begin{align*}
x - \frac{y}{y'} &= -x\\
\frac{y}{y'} &= 2x\\
y' &= \frac{y}{2x}\\
\int \frac{1}{y}dy &= \int \frac{1}{2x}dx\\
\text{ln}(y) &= \frac{1}{2}\text{ln}(|x|)+c\\
y &= \sqrt[]{e^{\text{ln}(|x|)}} \cdot e^c\\
y &= c \cdot \sqrt[]{|x|}\\
\end{align*}
\begin{align*}
\text{for } x &> 0 & \text{for } x &< 0\\
y &= c \cdot \sqrt[]{x} & y &= c \cdot \sqrt[]{-x}
\end{align*}
Since the constant $c$ in the solution does not affect the symmetry of the function, then by setting $c=1$ we obtain the following 2-cycle which will cycle for any initial guess $x_0 \not= 0$
$$f(x) = \sqrt[]{|x|}$$
\begin{center}
\includegraphics[scale = 1]{2-cycle.png}
\end{center}
\subsection{3-cycles}
To find 3-cycles, we will assume $f(x) = x^p$ and apply Newton's Method to obtain
\begin{align*}
x_{n+3} &= \left(1 - \frac{1}{p}\right)x_{n+2}\\
&= \left(1 - \frac{1}{p}\right)^2x_{n+1}\\
&= \left(1 - \frac{1}{p}\right)^3x_n
\end{align*}
\newline
Since this is a 3-cycle and $x_{n+2}$ is the third point in the 3-cycle, we make $x_{n+3} = x_n$ thus creating a repeating cycle. Since we know that $x_{n+3} = x_n$, then
$$
x_{n+3} = \left(1 - \frac{1}{p}\right)^3x_n
$$
can simplify to
$$
1 = \left(1 - \frac{1}{p}\right)^3
$$
Solving for $p$, we find
$$
p = \frac{1}{1 - \sqrt[3]{1}}
$$
\noindent Using the root 1 does not yield an answer we can use, but using the other two true cubic roots of one, ($-\frac{1}{2}\pm\frac{i*\sqrt[]{3}}{2}$), we find that
$$
p = \frac{1}{1 - \sqrt[3]{1}} = \frac{1}{\frac{3}{2} \pm \frac{\sqrt[]{3}i}{2}}
$$
Based on the solution from the paper \textit{Sometimes Newton's Method Always Cycles} \cite{Sometimes}, they found that when they used the other roots of $p$, \\
$$
p = \frac{3 \pm \sqrt[]{3}i}{6}
$$
\noindent Which, when simplified, come out to be the exact same.\\
\newline
\noindent Since we have found $p$, our initial condition of $f(x) = x^p$ can now be converted into a 3-cycle\footnote{This will go into the complex plane since this is raised to a complex number.}:
$$
f(x) = x^\frac{3 \pm \sqrt[]{3}i}{6}
$$
\noindent Now let us consider the function $f(x)$ that we have just found and apply Newton's Method three times to it to verify that we cycle back to the starting point. Let's take a starting value, $x_0 = 1$.
\begin{align*}
x_1 &= 1 - \frac{1^{\frac{3 + \sqrt[]{3}i}{6}}}{(\frac{3 + \sqrt[]{3}i}{6}) \cdot 1^{\frac{3 + \sqrt[]{3}i}{6} - 1}}\\
&= -\frac{1}{2} + \frac{\sqrt[]{3}i}{2}\\
x_2 &= \left(-\frac{1}{2} + \frac{\sqrt[]{3}i}{2}\right) - \frac{(-\frac{1}{2} + \frac{\sqrt[]{3}i}{2})^{\frac{3 + \sqrt[]{3}i}{6}}}{(\frac{3 + \sqrt[]{3}i}{6}) \cdot (-\frac{1}{2} + \frac{\sqrt[]{3}i}{2})^{\frac{3 + \sqrt[]{3}i}{6} - 1}}\\
&= -\frac{1}{2} - \frac{\sqrt[]{3}i}{2}\\
x_3 &= \left(-\frac{1}{2} - \frac{\sqrt[]{3}i}{2}\right) - \frac{(-\frac{1}{2} - \frac{\sqrt[]{3}i}{2})^{\frac{3 + \sqrt[]{3}i}{6}}}{(\frac{3 + \sqrt[]{3}i}{6}) \cdot (-\frac{1}{2} - \frac{\sqrt[]{3}i}{2})^{\frac{3 + \sqrt[]{3}i}{6} - 1}}\\
&= 1
\end{align*}
When plotted in the complex plane, we get the following graph:
\begin{center}
{\centering \includegraphics[scale = 0.8]{3-cycle.png}}\\
\end{center}
\subsection{4-cycles}
In order to find a function that will give us a 4-cycle we will assume $f(x) = x^p$ and use the same techniques used when finding the 3-cycle function to obtain
\begin{align*}
x_{n+4} &= \left(1 - \frac{1}{p}\right)x_{n+3}\\
&= \left(1 - \frac{1}{p}\right)^2x_{n+2}\\
&= \left(1 - \frac{1}{p}\right)^3x_{n+1}\\
&= \left(1 - \frac{1}{p}\right)^4x_n
\end{align*}
This can be simplified to
$$
1 = \left(1 - \frac{1}{p}\right)^4
$$
Solving for $p$, we find
$$
p = \frac{1}{1 - \sqrt[4]{1}}
$$
Here we find that the roots $\pm 1$ will not give us an answer we can use because $+1$ will give us an undefined $p$ and $-1$ will give us $p=\frac{1}{2}$, which does not cycle, but using the other two fourth roots of one, $\pm i$, we obtain
$$
p = \frac{1}{1 - \sqrt[4]{1}} = \frac{1}{1 \pm i} = \frac{1 \pm i}{2}
$$
Having found $p$, we can now obtain our 4-cycle function
$$
f(x) = x^{\frac{1 \pm i}{2}}
$$
Now let us verify that this function does cycle between four points by setting the starting value $x_0 = 1$.
\begin{align*}
x_1 &= 1 - \frac{1^{\frac{1 + i}{2}}}{(\frac{1 + i}{2}) \cdot 1^{\frac{1 + i}{2} - 1}}\\
&= i\\
x_2 &= i - \frac{i^{\frac{1 + i}{2}}}{(\frac{1 + i}{2}) \cdot i^{\frac{1 + i}{2} - 1}}\\
&= -1\\
x_3 &= (-1) - \frac{(-1)^{\frac{1 + i}{2}}}{(\frac{1 + i}{2}) \cdot (-1)^{\frac{1 + i}{2} - 1}}\\
&= -i\\
x_4 &= (-i) - \frac{(-i)^{\frac{1 + i}{2}}}{(\frac{1 + i}{2}) \cdot (-i)^{\frac{1 + i}{2} - 1}}\\
&= 1
\end{align*}
When plotted in the complex plane, we get the following graph:
\begin{center}
\includegraphics[scale = 0.7]{4-cycle.png}
\end{center}
\subsection{k-cycles}
Jumping ahead to the undetermined amount of cycles, k-cycles, we obtain
$$
x_{n+k} = \left(1 - \frac{1}{p}\right)^k \cdot x_n
$$
This equation shows that if we put any arbitrary number in for $x_{n+k}$ or $x_n$ that this will not affect the outcome and the below equation. Based on algebra, we can divide by the same numbers leaving us with 1.
$$
1 = \left(1 - \frac{1}{p}\right)^k \cdot 1
$$
Using and implementing the same axiom theorems, steps, and techniques we used with 3-cycles and 4-cycles for k-cycles, we obtain
$$
1 = \left(1 - \frac{1}{p}\right)^k
$$
Solving for $p$ we obtain
$$
p = \frac{1}{1 - \sqrt[k]{1}}
$$
For any $k$, we find that if the roots are $\pm 1$. They are unusable because $+1$ will give us an undefined $p$ and $-1$ will give us $p=\frac{1}{2}$, which does not cycle, but we can use the other $k^{\text{th}}$ roots of 1 to solve for $p$.\\
\newline
There is another way to find what $p$ is without using Newton's formula. First, we must go back to the formula we used for k-cycles since the formula is similar to this formula.
$$
1 = \left(1 - \frac{1}{p}\right)^k
$$
Since we are using the generic version of this formula, we must change a couple parts about this formula and even simplify this formula.
\begin{align*}
x_{n+k} &= \left(1 - \frac{1}{p}\right)^k \cdot x_n\\
x_n \cdot x_k &= \left(1 - \frac{1}{p}\right)^k \cdot x_n\\
x_k &= \left(1 - \frac{1}{p}\right)^k
\end{align*}
From the paper Sometimes Newton's Method Always Cycles \cite{Sometimes}, we can note that $p$ can be stated in a different way.
$$
p = a + (b \cdot i)
$$
There are three properties about our new generic formula.\\
\begin{enumerate}
\item Converge\\
\newline
$\left|1 - \frac{1}{p}\right| < 1$ \\
\newline
$\left|1 - \frac{1}{a + (b \cdot i)}\right| < 1$
\item Diverge\\
\newline
$\left|1 - \frac{1}{p}\right| > 1$ \\
\newline
$\left|1 - \frac{1}{a + (b \cdot i)}\right| > 1$
\item Constant\\
\newline
$\left|1 - \frac{1}{p}\right| = 1$ \\
\newline
$\left|1 - \frac{1}{a + (b \cdot i)}\right| = 1$
\end{enumerate}
To help us further understand what is happening in this formula, we must solve for a.
\begin{align*}
1 &= \left|1 - \frac{1}{a + (b \cdot i)}\right| \\
1 &= \left|1 - \frac{1}{(a+bi)}\frac{(a-bi)}{(a-bi)}\right|\\
1 &= \left|1 - \frac{a - bi}{a^2 + b^2}\right|\\
1 &= \left|\frac{a^2 + b^2 - a + bi}{a^2 + b^2}\right|\\
1 &= \left|\frac{a^2 + b^2 - a}{a^2 + b^2} + \frac{bi}{a^2 + b^2}\right|\\
1 &= \sqrt[]{\frac{(a^2 + b^2 - a)^2}{(a^2 + b^2)^2} + \frac{b^2}{(a^2 + b^2)^2}}\\
1 &= \frac{a^4 + 2a^2 b^2 - 2a^3 - 2ab^2 + a^2 + b^4 + b^2}{a^4 + 2a^2 b^2 + b^4}\\
a^4 + 2a^2 b^2 + b^4 &= a^4 + 2a^2 b^2 - 2a^3 - 2ab^2 + a^2 + b^4 + b^2 \\
0 &= -2a^3 - 2ab^2 + a^2 + b^2\\
2a^3 + 2ab^2 &= a^2 + b^2\\
2a(a^2 + b^2) &= a^2 + b^2\\
2a &= \frac{a^2 + b^2}{a^2 + b^2}\\
2a &= 1\\
a &= \frac{1}{2}
\end{align*}
\newline In the paper, Sometimes Newton's Method Always Cycles \cite{Sometimes}, the authors mention the function $f(x) = x^p$ can be rewritten as
$$
f(x) = x^{a+(b \cdot i)}
$$
When we did the calculations for this formula, we found that $f(x)$ also can be
$$
f(x) = x^{a-(b \cdot i)}
$$
Since the function cycles, having the signs change is arbitrary. As long as the initial choice is constant throughout the rest of the calculations. So then, all we have left is to find $b$.\\
\newline
Now that we know $a = \frac{1}{2}$, we can obtain the value for $b$ in the function $f(x) = x^{\frac{1}{2}+(b \cdot i)}$.
\begin{align*}
x_1 &= 1 - \frac{1}{\frac{1}{2} + (b \cdot i)}\\
&= 1 - \frac{\frac{1}{2} - bi}{\frac{1}{4} + b^2}\\
&=\frac{\frac{1}{4} + b^2}{\frac{1}{4} + b^2} - \frac{\frac{1}{2} - bi}{\frac{1}{4} + b^2}\\
&= \frac{\frac{1}{4} + b^2 - \frac{1}{2} + bi}{\frac{1}{4} + b^2}\\
&= \frac{1 + 4b^2 - 2 + 4bi}{1 + 4b^2}\\
&= \frac{4b^2 - 1}{4b^2 + 1} + \frac{4b}{4b^2 + 1}i
\end{align*}
Since $b$ is now the only variable we do not know, we need to find it to make sure that the function is sound. But before we do that, we need to understand the cycle itself. For this, we need to look at an example of a cycle.\\
\newline
The figures below are examples of converging and diverging cycles. What makes a function converge or diverge is the value of a.\\
\begin{enumerate}
\item Converge\\
\newline
$a > \frac{1}{2}$ \\
\item Diverge\\
\newline
$a < \frac{1}{2}$
\end{enumerate}
\begin{center}
\includegraphics[scale = 0.65]{3-cycle_converging.png}\\
\includegraphics[scale = 0.7]{3-cycle_converging2.png}\\
\includegraphics[scale = 0.80]{3-cycle_converging3.png}
\end{center}
We first must break the cycle down into more basic parts.
Since each iteration is a point with two components, a real and an imaginary part, then we can treat them as right triangles and use trigonometry to find cos($\alpha$). In this case the real part of the equation will be the adjacent side and the imaginary part will be the opposite side of the triangle, so then we have to calculate the hypotenuse of this triangle.
\begin{align*}
h &= \sqrt[]{\left(\frac{4b^2 - 1}{4b^2 + 1}\right)^2 + \left(\frac{4b}{4b^2 + 1}\right)^2}\\
&= \sqrt[]{\frac{16b^4 - 8b^2 + 1 + 16b^2}{16b^4 + 8b^2 + 1}}\\
&= \sqrt[]{\frac{16b^4 + 8b^2 + 1}{16b^4 + 8b^2 + 1}}\\
&= 1
\end{align*}
Now that we know what the hypotenuse is, we can now find what $b$ is. The variable $\alpha$ will be useful to help find $b$ because $\alpha$ is a known variable since it is the angle that is between the hypotenuse and the adjacent side of the triangle that was created earlier. We can express this through the following equation:\\
$$
\text{cos}(\alpha) = \frac{(\frac{4b^2 - 1}{4b^2 + 1})}{1}
= \frac{4b^2 - 1}{4b^2 + 1}
$$
When we look at the cycle as a whole, we must note that for each point within the cycle, we can see that there are subsections of the cycle, which are created by the points within the cycle. These points are extremely meaningful in trying to understand what the value of $b$ is. For this, we must introduce one new variable and reintroduce a known variable, $k$ and $m$. $k$ is the number of points in the cycle, thus the meaning of 2- cycle, 3-cycle, and k-cycle. $m$ is the length between points in the cycle, which is the subsection of cycle we mentioned earlier. Since a cycle, no matter the form, can be summarized as a circle, we can state that a full cycle has a value of 2$\pi$. Now knowing this, we now understand what $\alpha$ is.
\begin{align*}
\alpha k &= 2\pi \\
\alpha &= \frac{2\pi}{k}
\end{align*}
Now to solve for $b$ which is the imaginary component.
\begin{align*}
\text{cos}\left(\frac{2\pi m}{k}\right) &= \frac{4b^2 - 1}{4b^2 + 1}\\
\text{cos}(\alpha) &= \frac{4b^2 - 1}{4b^2 + 1}\\
(4b^2 + 1)(\text{cos}(\alpha)) &= (4b^2 - 1)\\
(4b^2(\text{cos}(\alpha)) + \text{cos}(\alpha) &= 4b^2 - 1\\
-4b^2 + (4b^2(\text{cos}(\alpha)) + \text{cos}(\alpha) &= -1\\
4b^2 (-1 + \text{cos}(\alpha)) + \text{cos}(\alpha) &= -1 \\
4b^2 (-1 + \text{cos}(\alpha)) &= -1 - \text{cos}(\alpha)\\
4b^2 &= \frac{-1 - \text{cos}(\alpha)}{-1 + \text{cos}(\alpha)}\\
b^2 &= \frac{1}{4} \cdot \frac{-1 - \text{cos}(\alpha)}{-1 + \text{cos}(\alpha)}\\
b &= \sqrt[]{\frac{1}{4} \cdot \frac{-1 - \text{cos}(\alpha)}{-1 + \text{cos}(\alpha)}}\\
b &= \pm \frac{1}{2} \cdot \sqrt[]{\frac{-1 - \text{cos}(\alpha)}{-1 + \text{cos}(\alpha)}}\\
b &= \pm \frac{1}{2} \cdot \sqrt[]{\frac{1 + \text{cos}(\alpha)}{1 - \text{cos}(\alpha)}}\\
b &= \pm \frac{1}{2} \cdot \text{cot}(\alpha)
\end{align*}
Now from this now we can obtain a general function $f(x) = x^{\frac{1}{2} \pm \frac{1}{2}\text{cot}(\frac{2\pi m}{k})i}$, where $k$ can be input in to create any $k$-cycle.
\subsection{Near Cycles}
These are near cycles which do not cycle perfectly between a $k$ number of points. Instead they group in the general area where the specific point is supposed to be. They are generated by keeping $a = \frac{1}{2}$ and $b$ does not satisfy $b = \pm \frac{1}{2} \cdot \text{cot}(\frac{2 \pi m}{k})i$. This creates a slightly faster (or slower), but more inaccurate answer for each iteration. These graphs are examples of near cycles.\\
\newline
\begin{center}
\includegraphics[scale = 0.75]{near-cycle.png}\\
\includegraphics[scale = 0.65]{7cycle.png}\\
\includegraphics[scale = 0.65]{near7.png}
\end{center}
\section{Other Questions}
\noindent After our investigation on Newton's Method cycling, we began thinking about if there are other functions aside from $x^p$ that would behave as a cycle. After many searches, we found a function that does not cycle, but instead it diverges for any initial guess when applying Newton's Method. We first start with the Newton Method with a function $T(x)$ such that
$$\frac{f'(x)}{f(x)} = \frac{T(x) + xT'(x)}{xT(x)}$$
Upon replacing this in the Newton Method we obtain
\begin{align*}
x_1 &= x_0 - \frac{f(x)}{f'(x)}\\
&= x_0 - \frac{x_0 T(x_0)}{T(x_0) + x_0 \cdot T'(x_0)}\\
&= x_0\left(1 - \frac{T(x_0)}{T(x_0) + x_0 \cdot T'(x_0)}\right)
\end{align*}
In order to obtain $T(x)$ we note that
\begin{align*}
\frac{T(x) + x \cdot T(x)}{x \cdot T(x)} = (\text{ln}(x\cdot T(x)))'
\end{align*}
Let us call $y = f(x)$ and combining this with our first condition we obtain
\begin{align*}
\frac{y'}{y} &= (\text{ln}(x \cdot T(x)))'\\
\frac{dy}{dx} \cdot \frac{1}{y} &= (\text{ln}(x \cdot T(x)))'\\
\int \frac{1}{y} dy &= \int (\text{ln}(x \cdot T(x)))' dx\\
\text{ln}(|y|) &= \text{ln}(x \cdot T(x)) + c\\
y &= x \cdot T(x) \cdot e^c, \forceindent e^c = D\\
f(x) &= D \cdot x \cdot T(x)
\end{align*}
For the quantity $\frac{T(x_0)}{T(x_0) + x_0 \cdot T'(x_0)}$, we must create a condition. We will set this quantity equal to k. We will also let $D = 1$.\\
\begin{align*}
k &= \frac{T(x_0)}{T(x_0) + x_0 \cdot T'(x_0)}\\
T(x_0) &= k \cdot T(x_0) + k \cdot x_0 \cdot T'(x_0)\\
k \cdot x_0 \cdot T'(x_0) &= T(x_0) - k \cdot T(x_0)\\
T'(x_0) &= \frac{T(x_0) - k \cdot T(x_0)}{k \cdot x_0}
\end{align*}
Now we will replace the $T'(x_0)$ with $\frac{dT}{dx}$, all the $T(x_0)$'s with $T$, and all the $x_0$ with $x$.
\begin{align*}
\frac{dT}{dx} &= \frac{T - k \cdot T}{k \cdot x}\\
\frac{dT}{dx} &= \frac{T \cdot (1 - k)}{k \cdot x}\\
\int \frac{1}{T} dT &= \frac{1 - k}{k} \int \frac{1}{x} dx\\
\text{ln}(T) &= \frac{1 - k}{k} \cdot \text{ln}(x) + c \\
T &= (e^{\text{ln}(x)})^{\frac{1 - k}{k}} \cdot e^c, \forceindent e^c = H\\
T &= H \cdot x^{\frac{1 - k}{k}}
\end{align*}
Therefore our solution is $T(x) = H \cdot x^{\frac{1 - k}{k}}$. Putting this back into our equation for $f(x)$ we obtain $f(x) = D \cdot x \cdot T(x) = D \cdot x \cdot H \cdot x^{\frac{1 - k}{k}}$. We can simplify this to $f(x) = A \cdot x^{\frac{1}{k}}$. This is a general method to find functions $f(x)$ where all points diverge and that are different from the ones mentioned within the paper Sometimes Newton's Method Always Cycles \cite{Sometimes}. For these functions, $k>2$ will still be of the form $x^p$, just that $p$ will be none of the values that the paper Sometimes Newton's Method Always Cycles, so the function above will be a different and new function similar to the form $x^p$.\\
\newline
Since the functions that we have looked at throughout this paper are symmetric, we questioned if there are functions that cycle asymmetrically. After researching this question, we found that there are functions that do cycle asymmetrically \cite{Wu}. But this requires PhD level mathematics that we currently do not have. \\
\newline
Another question we asked ourselves was what would happen if Newton's Method was multiplied by a constant, $h$. In other words, how would a weighted Newton's Method cycle? This is what deduced from multiplying the method by $h$. For this proof, it must be noted that $x_{n+1} = x_n$.
\begin{align*}
x_{n+1} &= x_n + \frac{h \cdot f(x_n)}{f'({x_n}^p)}\\
&= x_n + \frac{h \cdot {x_n}^p}{p \cdot {x_n}^{p-1}}\\
&= x_n + \frac{h \cdot x_n}{p}\\
&= \left(1 + \frac{h}{p}\right)^k \cdot x_n\\
1 &= \left(1 + \frac{h}{p}\right)^k
\end{align*}
Here we find that $p = \frac{h}{1 - \sqrt[k]{1}} = h(a + bi)$. Here are a couple of examples comparing the original cycle with its weighted counterpart:\\
\\
\textbf{3-cycle, h = 1} (original 3-cyle)
\begin{align*}
x_0 &= 1\\
x_1 &= -\frac{1}{2} + \frac{\sqrt[]{3}i}{2}\\
x_2 &= -\frac{1}{2} - \frac{\sqrt[]{3}i}{2}\\
x_3 &= 1
\end{align*}
\textbf{3-cycle, h = 2} (weighted)
\begin{align*}
x_0 &= 1\\
x_1 &= 1 - \frac{3}{3 - \sqrt[]{3}i}\\
x_2 &= \frac{\sqrt[]{3}i - 1}{8}\\
x_3 &= -\frac{1}{8}
\end{align*}
\textbf{4-cycle, h = 1} (original 4-cycle)
\begin{align*}
x_0 &= 1\\
x_1 &= i\\
x_2 &= -1\\
x_3 &= -i\\
x_4 &= 1
\end{align*}
\textbf{4-cycle, h = 2} (weighted)
\begin{align*}
x_0 &= 1\\
x_1 &= \frac{1}{2} + \frac{i}{2}\\
x_2 &= \frac{i}{2}\\
x_3 &= -\frac{1}{4} + \frac{i}{4}\\
x_4 &= -\frac{1}{4}
\end{align*}
\begin{center}
\includegraphics[scale = 0.8]{weighted4cycle.png}\
\end{center}
After completing a couple of calculations for 3 and 4 cycles with different values of $h$, we found that multiplying Newton's Method by any constant would disrupt the cycle to the point that the cycle would no longer be a cycle, but rather, a converging or diverging function depending on the value of $h$. In fact, we found it interesting that the function continued to act like a cycle in the case where $h = 2$, in the sense that when the cycle came back to the same line as the original point, but at a smaller coordinate. It appears to be making a inward spiral to the center, therefore converging to 0. %Since we are taking the derivative of the original function, we would never reach the center, but slowly reaching a more exact number that is close, but not equal to the center.
\newline
\\We found the behavior for $h > 1$ converges and for $h < 1$ diverges. We noted that the type of cycle also changes as $h$ changes since it multiplies $bi$ which is what determines the type of cycle we have. We also found that the shape of the graph was congruent every time that the points crossed the $x$-axis.
\newline
\\After this, we wondered if there was a way to create a weighted cycle with a constant radius, so we used the same techniques from our generic formula.
\begin{align*}
1 &= \left|1 - \frac{h}{a + (b \cdot i)}\right| \\
1 &= \left|1 - \frac{h}{(a+bi)}\frac{(a-bi)}{(a-bi)}\right|\\
1 &= \left|1 - \frac{ha - hbi}{a^2 + b^2}\right|\\
1 &= \left|\frac{a^2 + b^2 - ha + hbi}{a^2 + b^2}\right|\\
1 &= \left|\frac{a^2 + b^2 - ha}{a^2 + b^2} + \frac{hbi}{a^2 + b^2}\right|\\
1 &= \sqrt[]{\frac{(a^2 + b^2 - ha)^2}{(a^2 + b^2)^2} + \frac{h^2b^2}{(a^2 + b^2)^2}}\\
1 &= \frac{a^4 + 2a^2 b^2 - 2ha^3 - 2hab^2 + h^2a^2 + b^4 + h^2b^2}{a^4 + 2a^2 b^2 + b^4}\\
a^4 + 2a^2 b^2 + b^4 &= a^4 + 2a^2 b^2 - 2ha^3 - 2hab^2 + h^2a^2 + b^4 + h^2b^2 \\
0 &= -2ha^3 - 2hab^2 + h^2a^2 + h^2b^2\\
2ha^3 + 2hab^2 &= h^2a^2 + h^2b^2\\
2ha(a^2 + b^2) &= h^2(a^2 + b^2)\\
2ha &= \frac{h^2(a^2 + b^2)}{a^2 + b^2}\\
2ha &= h^2\\
a &= \frac{h}{2}
\end{align*}
Since $a = \frac{h}{2}$, then we find that the weighted function will still converge or diverge depending on the value of $h$ since $a \not= \frac{1}{2}$. The only way for this condition to be met would be when $h = 1$, but that would be an unweighted function.
\newpage
\section{Conclusion}
\noindent With this new found knowledge, we can conclude that Newton's Method does cycle for functions with any initial non-trivial guesses. We have looked into this for all cases and proving for the first three types of cycles, 2-cycles, 3-cycles and 4-cycles. After reaching the conclusion that there are functions that do iterate, we moved forward to the generic function of k-cycles, where we found that functions exist for any number of cycles to satisfy Newton's Method. Proving this, we then became curious about the behaviors of these functions in terms of convergence, divergence or having a constant radius. This brought forth a new idea, near cycles. We discovered that there are functions that behave similarly to cycles, but do not actually cycle perfectly. After our discoveries about these ideas, we began to raise other, more outlying, questions. From these questions, we found another type of function that cycles and is not in the form $f(x) = x^p$, that there is a way for the method to cycle asymmetrically, and what happens when we multiply Newton's Method cycles by a constant. \\
\newline
Newton's Method always cycles!
\newpage
\bibliographystyle{plain}
\bibliography{capstone}
\end{document}
